Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
贴一份自己写的代码看的是别人的思路,主要是没弄清楚题目的本意,最后实现是自己思考实现的,用vjudge交了很多oj都AC,应该没bug了。 #include <cstdio> #include <cmath> #include <algorithm> #define maxn 1001 using namespace std; struct Point{ Point(double a,double b):x(a),y(b){} Point(){} double x,y; }p[maxn],ch[maxn]; int N; typedef Point Vector; const double eps=1e-10; int dcmp(double x) { if(fabs(x)<eps) return 0; return x>0?1:-1; } Vector operator-(Point a,Point b){ return Vector(a.x-b.x,a.y-b.y); } bool cmp(Point a,Point b){ return a.x<b.x||(a.x==b.x&&a.y<b.y); } int Cross(Vector a,Vector b){ return dcmp(a.x*b.y-a.y*b.x); } bool Judge() { if(N<6) return 0; int i,k,m=0,w; sort(p,p+N,cmp); for(i=0;i<N;++i) { while(m>1&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<0) m--; ch[m++]=p[i]; } k=m; for(i=N-2;i>=0;--i) { while(m>k&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<0) m--; ch[m++]=p[i]; } if(N>1) m--; k=-1; for(i=1;i<m-1;++i) if(Cross(ch[i+1]-ch[i],ch[i]-ch[i-1])!=0) { k=i; break; } if(k==-1) return 0; int len; for(i=k;;i=(i+1)%m) { len=0,w=i; while(Cross(ch[(w+1)%m]-ch[w],ch[(w+2)%m]-ch[w])==0) { len++; w=(w+1)%m; } if(len==0) return 0; i=w; if(i+1==k) break; } return 1; } int main() { int T,i; double x,y; scanf("%d",&T); while(T--) { scanf("%d",&N); for(i=0;i<N;++i) { scanf("%lf%lf",&x,&y); p[i]=Point(x,y); } if(Judge()) puts("YES"); else puts("NO"); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator