QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#548029 | #9177. String and Nails | paramec1um# | WA | 0ms | 13240kb | C++20 | 1.7kb | 2024-09-05 14:52:04 | 2024-09-05 14:52:06 |
Judging History
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: 100
Accepted
time: 0ms
memory: 13240kb
input:
3 1 1 2 4 3 1
output:
YES 1 1 2 4
result:
ok Everything ok
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 13164kb
input:
1 1000000000 0
output:
NO
result:
wrong answer Jury has a bigger answer