POJ 1474 Video Surveillance

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

/*

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<cmath>
#include<cstdio>
#include<algorithm>
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<n;i++) res+=((p[i]-p[1])^(p[i+1]-p[1]));
    return res>eps;
}
bool check(Line a,Line b,Line c) // 判断 a，b的交点是否在c的左侧包括线上
{
    Point d=a&b; return ((d-c.s)^(c.e-c.s))<eps;
}
int from(Line a) //  up left down right 
{
    Point A=a.e-a.s;
    if(A.x==0&&A.y>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<f2;
    return ((a.s-b.s)^(b.e-b.s))<eps;
}
bool solve()
{
    sort(l+1,l+n+1,cmp); int top=1;
    for(int i=2;i<=n;i++) if(from(l[i])!=from(l[top])) l[++top]=l[i];
    Line up,left,right,down;
    up=l[1];left=l[2];down=l[3];right=l[4];
//printf("    up : (%.2lf,%.2lf) -> (%.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;
}
/*
bian

8
1 0
1 1
0 1
0 3
1 3
1 2
2 2
2 0

dian

8
1 1
0 1
0 2
1 2
1 1
2 1
2 0
1 0


*/