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 |
为什么WA!求大神#include <stdio.h> #include <math.h> //gcc需加-lm参数 #include <cmath> #define eps 0.0000001 #define PI 3.141592654 //PI = acos(-1.0); #define zero(x)(((x)>0?(x):-(x))<eps) using namespace std; struct POINT { double x; double y; }; struct line { POINT a,b; }; double dist(POINT p1,POINT p2) { return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)); } double multiply(POINT sp,POINT ep,POINT op) { return((sp.x-op.x)*(ep.y-op.y)-(ep.x-op.x)*(sp.y-op.y)); } double xmult(POINT p1,POINT p2,POINT p0) { return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y); } //判断点是否在线段上 int dog(POINT p,line l) { return zero(xmult(p,l.a,l.b))&&(l.a.x-p.x)*(l.b.x-p.x)<eps&&(l.a.y-p.y)*(l.b.y-p.y)<eps; } int dog1(POINT p,line l) { return dog(p,l)&&(!zero(p.x-l.a.x)||!zero(p.y-l.a.y))&&(!zero(p.x-l.b.x)||!zero(p.y-l.b.y)); } int Graham_scan(POINT PointSet[],POINT ch[],int n) { int i,j,k=0,top=2,len; POINT tmp; for(i=1; i<n; i++) if ( PointSet[i].y<PointSet[k].y || (PointSet[i].y==PointSet[k].y) && (PointSet[i].x<PointSet[k].x) ) k=i; tmp=PointSet[0]; PointSet[0]=PointSet[k]; PointSet[k]=tmp; // 现在PointSet中y坐标最小的点在PointSet[0] for (i=1; i<n-1; i++) /* 对顶点按照相对PointSet[0]的极角从小到大进行排序,极角相同的按照距离PointSet[0]从近到远进行排序 */ { k=i; for (j=i+1; j<n; j++) if ( multiply(PointSet[j],PointSet[k],PointSet[0])>0 || // 极角更小 (multiply(PointSet[j],PointSet[k],PointSet[0])==0) && /* 极角相等,距离更短 */ dist(PointSet[0],PointSet[j])<dist(PointSet[0],PointSet[k]) ) k=j; tmp=PointSet[i]; PointSet[i]=PointSet[k]; PointSet[k]=tmp; } ch[0]=PointSet[0]; ch[1]=PointSet[1]; ch[2]=PointSet[2]; //用数组模拟栈,top为栈顶 for (i=3; i<n; i++) { while (multiply(PointSet[i],ch[top],ch[top-1])>=0) top--; ch[++top]=PointSet[i]; } len=top+1; return len; } int main() { int N,L; scanf("%d",&L); while(L--) { scanf("%d",&N); int i,j; POINT PointSet[1001],ch[1001]; for(i=0; i<N; i++) { scanf("%lf%lf",&PointSet[i].x,&PointSet[i].y); } j=Graham_scan(PointSet,ch,N); // Graham_scan(PointSet,ch,N); int s=0,k,ss=0; line l; int q=0; for(i=1; i<j; i++) { if(ch[0].y==ch[i].y) q++; else break; } l.a=ch[0]; l.b=ch[q]; for( k=0; k<N; k++) { if(dog1(PointSet[k],l)) { s++; break; } } // printf("%d %d\n",s,q); for(i=q; i<j; i++) { l.a=ch[q]; l.b=ch[q+1]; for( k=0; k<N; k++) { if(dog1(PointSet[k],l)) { s++; break; } } } // printf("%d\n",s); for( k=0; k<N; k++) { l.a=ch[0]; l.b=ch[j-1]; if(dog1(PointSet[k],l)) { s++; break; } } // printf("%d\n",s); if(s==j) printf("YES\n"); else printf("NO\n"); } return 0; } /* 1)此题需要判断“凸包上每条边至少包含原多边形三个点”。成立就是“YES”。 我试的判断“多边形上 所有点 在凸包上”,WA!! (2)注意:所有点共线时,结果为“NO”。 */ Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator