POJ 1474 Video Surveillance-白红宇

POJ 1474 Video Surveillance

阅读量：4353 次

发布时间：2019-06-07

本文共 2592 字，大约阅读时间需要 8 分钟。

只需要判断就行了不需要正宗的半平面交

/*Point operator & (Line A,Line B){    Point C=A.s;    double t=((A.s-B.s)^(B.s-B.e))/((A.s-A.e)^(B.s-B.e));    C.x+=(A.e.x-A.s.x)*t; C.y+=(A.e.y-A.s.y)*t;    return C;}半平面交 1.首先规定逆时针给点 判断的时候直接求有向面积 面积为负则是顺时针给的点 2.极角排序 （可以去重 留下靠左的一个）3.模拟双端队列 判断队列尾部两线的交点和头部两线的交点在新加入线段哪一侧     左侧即合法 直接加入 右侧即不合法 删掉堆尾4.因为我们 3 过程中始终保持队列数量至少为2 所以最后判断头部和尾部的合法性    剩下的边<=2条的话 说明不存在内核NOTE: 此题特殊 之存在上下左右方向的线  最后决定的线也只有4条 可以直接判断 不用打半平面交    所以&交点也不需要考虑两线平行的情况*/#include
     
      #include
      
       #include
       
        using namespace std;const int N=150;const double eps=1e-9;struct Point{    double x,y;Point(){}    Point(double _x,double _y){x=_x,y=_y;}}p[N];struct Line{    Point s,e;Line(){}    Line(Point _s,Point _e){s=_s,e=_e;} }l[N],q[N];int n,T;Point operator - (Point A,Point B) {
   return Point(A.x-B.x,A.y-B.y);} double operator ^ (Point A,Point B) {
   return A.x*B.y-A.y*B.x;} Point operator & (Line A,Line B){    Point C=A.s;    double t=((A.s-B.s)^(B.s-B.e))/((A.s-A.e)^(B.s-B.e));    C.x+=(A.e.x-A.s.x)*t; C.y+=(A.e.y-A.s.y)*t;    return C;}bool Isf() // 判断给出的点是否是逆时针的{    double res=0;    for(int i=2;i
        
         eps;}bool check(Line a,Line b,Line c) // 判断 a，b的交点是否在c的左侧包括线上{    Point d=a&b; return ((d-c.s)^(c.e-c.s))
         
          0) return 1;    else if(A.x<0&&A.y==0) return 2;    else if(A.x==0&&A.y<0) return 3;    else return 4;}bool cmp(Line a,Line b){    int f1=from(a),f2=from(b);    if(f1!=f2) return f1
          
            (%.2lf,%.2lf)\n",l[1].s.x,l[1].s.y,l[1].e.x,l[1].e.y);//printf(" left : (%.2lf,%.2lf) -> (%.2lf,%.2lf)\n",l[2].s.x,l[2].s.y,l[2].e.x,l[2].e.y);//printf(" down : (%.2lf,%.2lf) -> (%.2lf,%.2lf)\n",l[3].s.x,l[3].s.y,l[3].e.x,l[3].e.y);//printf(" right : (%.2lf,%.2lf) -> (%.2lf,%.2lf)\n",l[4].s.x,l[4].s.y,l[4].e.x,l[4].e.y);//printf(" up : (%.2lf,%.2lf)\n",up.x,up.y);//printf(" left : (%.2lf,%.2lf)\n",left.x,left.y);//printf(" down : (%.2lf,%.2lf)\n",down.x,down.y);//printf(" right : (%.2lf,%.2lf)\n",right.x,right.y); if(up.s.x-down.s.x<-eps)return 0; if(left.s.y-right.s.y<-eps) return 0; return 1;}int main(){ while(scanf("%d",&n)&&n) { T++; for(int i=1;i<=n;i++) { double x,y; scanf("%lf%lf",&x,&y); p[i]=Point(x,y); } if(!Isf()) for(int i=1;i<=(n>>1);i++) swap(p[i],p[n-i+1]); p[n+1]=p[1]; for(int i=1;i<=n;i++) l[i]=Line(p[i],p[i+1]); printf("Floor #%d\n",T); if(solve()) puts("Surveillance is possible."); else puts("Surveillance is impossible."); putchar('\n'); } return 0;}/*bian81 01 10 10 31 31 22 22 0dian81 10 10 21 21 12 12 01 0*/