QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#548025#9177. String and Nailsparamec1um#WA 2ms12972kbC++201.7kb2024-09-05 14:51:292024-09-05 14:51:30

Judging History

你现在查看的是最新测评结果

  • [2024-09-05 14:51:30]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:12972kb
  • [2024-09-05 14:51:29]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define IN inline
const int maxn=2e5+10;
struct Point{
    double x,y;
	int id=0;
    //排序为Andrew凸包算法做准备
    IN bool operator<(const Point &t)const {//按照x排序
        if(x!=t.x) return x<t.x;
        return y<t.y;//x相同按照y排序
    }
    IN Point operator+(const Point &t)const {return {x+t.x,y+t.y};}
    IN Point operator-(const Point &t)const {return {x-t.x,y-t.y};} 
    IN Point operator*(const double &t)const {return {x*t,y*t};}//数乘
    IN double operator*(const Point &t)const {return x*t.y-y*t.x;} //叉积 
    friend ostream & operator<<(ostream &out,const Point &t);
};
ostream & operator<<(ostream &out,const Point &t){out<<t.x<<' '<<t.y;return out;}
IN double sqr(double x){return x*x;}
IN double dis(Point a){return sqr(a.x)+sqr(a.y);}//距离平方
int top,n,f;
Point a[maxn],stk[maxn];
void Andrew(){
    sort(a+1,a+1+n);
    for(int i=1;i<=n;++i){
        while(top>1 && ((a[i]-stk[top-1])*(stk[top]-stk[top-1]))<0)--top;
        stk[++top]=a[i];
    }
    int tmp=top;
    for(int i=n-1;i>=1;--i){
        while(top>tmp && ((a[i]-stk[top-1])*(stk[top]-stk[top-1]))<0)--top;
        stk[++top]=a[i];
    }
    --top;//去掉重复的1号点
}
void solve(){
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>a[i].x>>a[i].y;
	}
	Andrew();
	//cout<<top<<'\n';
	//for(int i=1;i<=top;++i)cout<<stk[i]<<'\n';
	if(top!=n)cout<<"NO\n";
	else{
		cout<<"YES\n";
		for(int i=1;i<n;++i)cout<<stk[i]<<'\n';
	}
	
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	fstream in("in.txt",ios::in);cin.rdbuf(in.rdbuf());
	int T=1;//cin>>T;
	while(T--)solve();
	return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 12972kb

input:

3
1 1
2 4
3 1

output:

NO

result:

wrong answer Jury has a bigger answer