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 |
Re:求大神指点In Reply To:求大神指点 Posted by:nofalpc at 2012-06-15 23:05:20 > #include<iostream> > #include<stdio.h> > #include<cmath> > #include<algorithm> > > using namespace std; > > const double eps=1e-8; > const int maxn=1000+10; > const double maxx=2e10; > const double pi=acos(-1.0); > int top; > > struct point{ > //平面上的点 > int x; > int y; > point(int x0=0,int y0=0) > { > //构造 > x=x0; > y=y0; > } > > point operator -(point b) > { > //减 表示向量AB=A-B,实际运算B-A; > return point(b.x-x,b.y-y); > } > > int operator %(point b) > { > //叉积 > return x*b.y-y*b.x; > } > }Null; > > > point yd(0,0); > int st[maxn]; > point pp[maxn]; > int n1; > point pt; > int pnum; > > double dist(point p1,point p2) > { > double px,py; > px=p1.x-p2.x; > py=p1.y-p2.y; > return sqrt(px*px+py*py); > } > > bool operator <(const point a,const point b) > { > int m=(pp[0]-a)%(pp[0]-b); > if(m>0) > { > return true; > } > else if(m==0&&(dist(pp[0],a)>dist(pp[0],b))) > { > return true; > } > return false; > } > > void graham(int n) > { > //三个以上的点集,以排序按Y-X > top=2; > st[0]=0; > st[1]=1; > st[2]=2; > int i; > for(i=2;i<=n;i++) > { > while((pp[st[top-1]]-pp[st[top]])%(pp[i]-pp[st[top-1]])>=0) > { > if(top==0)break; > top--; > } > top++; > st[top]=i; > } > return ; > } > > void init() > { > int i; > pt.y=-1; > for(i=0;i<n1;i++) > { > scanf("%d %d",&pp[i].x,&pp[i].y); > if(pt.y==-1||pp[i].y<pt.y) > { > pt=pp[i]; > pnum=i; > } > if(pp[i].y==pt.y&&pp[i].x<pt.x) > { > pt=pp[i]; > pnum=i; > } > } > swap(pp[pnum],pp[0]); > sort(pp+1,pp+n1); > pp[n1]=pp[0]; > return ; > } > > void work(int n) > { > bool ok=true; > if(top<2) > { > ok=false; > } > int i; > for(i=2;i<top;i++) > { > if(st[i]-st[i-1]==1) > { > ok=false; > break; > } > } > if(i==top&&fabs((pp[n-1]-pp[n-2])%(pp[n-1]-pp[n]))>eps) > { > ok=false; > } > if(ok) > { > printf("YES\n"); > } > else > { > printf("NO\n"); > } > return ; > } > int main() > { > int t; > scanf("%d",&t); > while(t--) > { > scanf("%d",&n1); > init(); > if(n1<6) > { > printf("NO\n"); > } > else > { > graham(n1); > work(n1); > } > } > //system("pause"); > return 0; > } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator