题意:给定一个多边形判断是否存在内核。
模板题。判断最后半面相交的半面数至少3个就行。
#include<cmath> #include<cstdio> #include<iostream> #include<algorithm> using namespace std; const int mm=111; typedef double DIY; struct point { DIY x,y; point() {} point(DIY _x,DIY _y):x(_x),y(_y) {} } g[mm]; point MakeVector(point &P,point &Q) { return point(Q.x-P.x,Q.y-P.y); } DIY CrossProduct(point P,point Q) { return P.x*Q.y-P.y*Q.x; } DIY MultiCross(point P,point Q,point R) { return CrossProduct(MakeVector(Q,P),MakeVector(Q,R)); } struct halfPlane { point s,t; double angle; halfPlane() {} halfPlane(point _s,point _t):s(_s),t(_t) {} halfPlane(DIY sx,DIY sy,DIY tx,DIY ty):s(sx,sy),t(tx,ty) {} void GetAngle() { angle=atan2(t.y-s.y,t.x-s.x); } } hp[mm],q[mm]; point IntersectPoint(halfPlane P,halfPlane Q) { DIY a1=CrossProduct(MakeVector(P.s,Q.t),MakeVector(P.s,Q.s)); DIY a2=CrossProduct(MakeVector(P.t,Q.s),MakeVector(P.t,Q.t)); return point((P.s.x*a2+P.t.x*a1)/(a2+a1),(P.s.y*a2+P.t.y*a1)/(a2+a1)); } bool cmp(halfPlane P,halfPlane Q) { if(fabs(P.angle-Q.angle)<1e-8) return MultiCross(P.s,P.t,Q.s)>0; return P.angle<Q.angle; } bool IsParallel(halfPlane P,halfPlane Q) { return fabs(CrossProduct(MakeVector(P.s,P.t),MakeVector(Q.s,Q.t)))<1e-8; } void HalfPlaneIntersect(int n,int &m) { sort(hp,hp+n,cmp); int i,l=0,r=1; for(m=i=1; i<n; ++i) if(hp[i].angle-hp[i-1].angle>1e-8)hp[m++]=hp[i]; n=m; m=0; q[0]=hp[0],q[1]=hp[1]; for(i=2; i<n; ++i) { if(IsParallel(q[r],q[r-1])||IsParallel(q[l],q[l+1]))return; while(l<r&&MultiCross(hp[i].s,hp[i].t,IntersectPoint(q[r],q[r-1]))>0)--r; while(l<r&&MultiCross(hp[i].s,hp[i].t,IntersectPoint(q[l],q[l+1]))>0)++l; q[++r]=hp[i]; } while(l<r&&MultiCross(q[l].s,q[l].t,IntersectPoint(q[r],q[r-1]))>0)--r; while(l<r&&MultiCross(q[r].s,q[r].t,IntersectPoint(q[l],q[l+1]))>0)++l; q[++r]=q[l]; for(i=l; i<r; ++i) g[m++]=IntersectPoint(q[i],q[i+1]); } int main() { int n,m,s=0; while(~scanf("%d",&n),n) { if(s) printf("\n"); for(int i=0; i<n; i++) scanf("%lf%lf",&g[i].x,&g[i].y); for(int i=0; i<n; i++) { hp[i]=halfPlane(g[(i+1)%n],g[i]); hp[i].GetAngle(); } HalfPlaneIntersect(n,m); printf("Floor #%d\n",++s); puts(m>2?"Surveillance is possible.":"Surveillance is impossible."); } return 0; }