> RT,抄的白书的半平面交板子,不会处理边界,于是把每条直线向外平移eps的长度再半平面交就可以了.
> #include<cstdio>
> #include<cmath>
> #include<algorithm>
> using namespace std;
> const int maxn=205;
> const double eps=1e-8;
> int cmp(double x){return x<-eps?-1:x>eps;}
> struct point{
>   double x,y;point(){}
>   point(double a,double b){x=a;y=b;}
>   void read(){scanf("%lf%lf",&x,&y);}
> }P[maxn],p[maxn];
> point operator +(point a,point b){return point(a.x+b.x,a.y+b.y);}
> point operator -(point a,point b){return point(a.x-b.x,a.y-b.y);}
> double cross(point a,point b){return a.x*b.y-a.y*b.x;}
> struct line{
>   point s,d;double arg;
>   bool operator <(const line &B)const{return cmp(arg-B.arg)==-1;}
>   line(){}
>   line(point a,point b){s=a;d=b;arg=atan2(d.y,d.x);}
>   void output(){
>     printf("(%f,%f)+(%f,%f)\n",s.x,s.y,d.x,d.y);
>   }
> }L[maxn],q[maxn];
> int n;
> bool onleft(line A,point B){
>   return cmp(cross(A.d,B-A.s))>0;
> }
> point mult(double t,point A){
>   return point(t*A.x,t*A.y);
> }
> point intersect(line A,line B){
>   double t=cross(B.d,A.s-B.s)/cross(A.d,B.d);
>   return A.s+mult(t,A.d);
> }
> point rot(point A,double arg){
>   return point(A.x*cos(arg)-A.y*sin(arg),A.x*sin(arg)+A.y*cos(arg));
> }
> int HPI(){
>   sort(L,L+n);
>   int head,tail;head=tail=0;q[tail++]=L[0];
>   for(int i=1;i<n;++i){
>     while(head+1<tail&&!onleft(L[i],p[tail-2]))tail--;
>     while(head+1<tail&&!onleft(L[i],p[head]))  head++;
>     q[tail++]=L[i];
>     if(head+1<tail&&cmp(cross(q[tail-1].d,q[tail-2].d))==0){
>       tail--;
>       if(onleft(q[tail-1],L[i].s))q[tail-1]=L[i];
>     }
>     if(head+1<tail)p[tail-2]=intersect(q[tail-1],q[tail-2]);
>   }
>   while(head+1<tail&&!onleft(q[head],p[tail-2]))tail--;
>   //  q[head].output();q[head+1].output();
>   if(tail-head<=2)return 0;
>   else return 1;
> }
> point normal(point A){return point(-A.y,A.x);}
> point operator *(const double &t,const point &A){return point(A.x*t,A.y*t);}
> int main(){
>   int tests=0;
>   while(scanf("%d",&n),n!=0){
>     for(int i=0;i<n;++i)P[i].read();P[n]=P[0];
>     for(int i=0;i<n;++i)L[i]=line(P[i]-eps*normal(P[i]-P[i+1]),P[i]-P[i+1]);
>     if(HPI())printf("Floor #%d\nSurveillance is possible.\n",++tests);
>     else printf("Floor #%d\nSurveillance is impossible.\n",++tests);
>     printf("\n");
>   }
>   return 0;
> }

• Re:为了避免对边界情况的讨论,可以对直线做微小扰动 (14) 2582426632 2019-08-27 16:36:14