|
Posted on 2009-09-25 23:28 Uriel 阅读(608) 评论(0) 编辑 收藏 引用 所属分类: POJ 、 计算几何
WA无数次啊。。。看了Discuss之后又WA数次才过。。。 1. n<=5,一律输出NO 2. 所有点共线,NO 3. 凸包上每条边上至少有三点,否则NO
/**//*Problem: 1228 User: Uriel Memory: 616K Time: 0MS Language: G++ Result: Accepted */
#include <math.h> #include <stdio.h> #include <stdlib.h> #include <memory.h>
#define eps 1e-8 #define MAXN 1005 #define zero(x) (((x)>0?(x):-(x))<eps)
struct point { double x,y; };
point P[MAXN],convex[MAXN]; int t,n,i,j,flag[MAXN],k;
//计算cross product (P1-P0)x(P2-P0) 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); }
//graham算法顺时针构造包含所有共线点的凸包,O(nlogn) point p1,p2; int graham_cp(const void* a,const void* b){ double ret=xmult(*((point*)a),*((point*)b),p1); return zero(ret)?(xmult(*((point*)a),*((point*)b),p2)>0?1:-1):(ret>0?1:-1); } void _graham(int n,point* p,int& s,point* ch){ int i,k=0; for (p1=p2=p[0],i=1;i<n;p2.x+=p[i].x,p2.y+=p[i].y,i++) if (p1.y-p[i].y>eps||(zero(p1.y-p[i].y)&&p1.x>p[i].x)) p1=p[k=i]; p2.x/=n,p2.y/=n; p[k]=p[0],p[0]=p1; qsort(p+1,n-1,sizeof(point),graham_cp); for (ch[0]=p[0],ch[1]=p[1],ch[2]=p[2],s=i=3;i<n;ch[s++]=p[i++]) for (;s>2&&xmult(ch[s-2],p[i],ch[s-1])<-eps;s--); }
//构造凸包接口函数,传入原始点集大小n,点集p(p原有顺序被打乱!) //返回凸包大小,凸包的点在convex中 //参数maxsize为1包含共线点,为0不包含共线点,缺省为1 //参数clockwise为1顺时针构造,为0逆时针构造,缺省为1 //在输入仅有若干共线点时算法不稳定,可能有此类情况请另行处理! //不能去掉点集中重合的点 int graham(int n,point* p,point* convex,int maxsize=0,int dir=1){ point* temp=new point[n]; int s,i; _graham(n,p,s,temp); for (convex[0]=temp[0],n=1,i=(dir?1:(s-1));dir?(i<s):i;i+=(dir?1:-1)) if (maxsize||!zero(xmult(temp[i-1],temp[i],temp[(i+1)%s]))) convex[n++]=temp[i]; delete []temp; return n; }
//判点是否在线段上,包括端点 int dot_online_in(point p,point l1,point l2) { return zero(xmult(p,l1,l2))&&(l1.x-p.x)*(l2.x-p.x)<eps&&(l1.y-p.y)*(l2.y-p.y)<eps; }
int main() { scanf("%d",&t); while(t--) { scanf("%d",&n); for(i=0;i<n;i++) { scanf("%lf %lf",&P[i].x,&P[i].y); } if(n<=5) { printf("NO\n"); continue; } k=0; for(i=1;i<n-1;i++) { if(xmult(P[0],P[n-1],P[i])!=0) { k=1; break; } } if(!k) { printf("NO\n"); continue; } int M=graham(n,P,convex,0,1); if(M==n) { printf("NO\n"); continue; } memset(flag,0,sizeof(flag)); for(i=0;i<n;i++) { for(j=0;j<M-1;j++) { if(dot_online_in(P[i],convex[j],convex[j+1])) { flag[j]++; } } if(dot_online_in(P[i],convex[M-1],convex[0])) { flag[M-1]++; } } k=0; for(i=0;i<M;i++) { if(flag[i]<3) { k=1; break; } } if(!k) { printf("YES\n"); } else { printf("NO\n"); } } system("PAUSE"); return 0; }
|