poj 1228 凸包
scturtle
posted @ 2010年9月17日 04:40
in algorithm
, 2319 阅读
题意给出一个凸包,问是否唯一。若某边上仅有由两个点,则易见可以加一个点扩充,形成另一个凸包。对数据无语。
#include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <algorithm> using namespace std; int sig(double d) { return fabs(d) < 1E-6 ? 0 : d < 0 ? -1 : 1; } struct Point{double x,y; bool operator < (const Point &p) const { return sig(x-p.x) != 0 ? x < p.x : sig(y-p.y) < 0; } }; double dis(Point a, Point b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } double cross(Point o, Point a, Point b) { return (a.x - o.x)*(b.y - o.y)-(b.x - o.x)*(a.y - o.y); } int graham(Point*p, int n, int*ch) { #define push(x) ch[len ++]=x #define pop() len -- sort(p, p+n); int len = 0, len0 = 1, i; for(i = 0; i < n; i ++) { while(len > len0 && sig(cross(p[ch[len-1]], p[ch[len-2]], p[i]))<=0) pop(); push(i); } len0 = len; for(i = n-2; i >= 0; i --) { while(len > len0 && sig(cross(p[ch[len-1]], p[ch[len-2]], p[i]))<=0) pop(); push(i); } return len-1; } #define maxn 1001 Point p[maxn]; int ch[maxn]; bool flag[maxn]; int flag2[maxn]; int main() { #ifndef ONLINE_JUDGE freopen("in","r",stdin); freopen("out","w",stdout); #endif int cas,i,j,n,m; scanf("%d",&cas); bool ok; while(cas--) { scanf("%d",&n); for(i=0;i<n;i++) scanf("%lf%lf",&p[i].x,&p[i].y); m=graham(p,n,ch); if(n<=5) {puts("NO");continue;}//加了这句才过…… memset(flag,0,sizeof(flag)); memset(flag2,0,sizeof(flag2)); for(i=0;i<m;i++) flag[ch[i]]=1; for(i=0;i<n;i++) if(!flag[i]) { for(j=1;j<m;j++) if(sig(cross(p[i],p[ch[j-1]],p[ch[j]]))==0) {flag2[j-1]|=2;flag2[j]|=1;} if(sig(cross(p[i],p[ch[m-1]],p[ch[0]]))==0) {flag2[m-1]|=2;flag2[0]|=1;} } ok=1; for(i=0;i<m;i++) if(flag2[i]<3) {ok=0;break;} if(ok) puts("YES"); else puts("NO"); } }