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:为了避免对边界情况的讨论,可以对直线做微小扰动 (2380) 2582426632 2019-08-27 16:35:02
  • Re:为了避免对边界情况的讨论,可以对直线做微小扰动 (14) 2582426632 2019-08-27 16:36:14