P4196 半平面交

· · 题解

之前那个方法遇到相反但长度不相等的向量就死了，所以改了下（

半平面交其他题解和 oi-wiki 已经讲解比较充分，主要说一下判断无解的细节
讨论区有人给出这样一组数据： 

3
4
0 0
3 0
3 1
0 1
4
4 0
5 0
5 1
4 1
3
0 0
4 0
0 2

现有题解唯一过的两篇一个是抄书一个是 n^2 暴力（

画出图来是有两个四边形只有一个公共点，所以答案应该为 0
这种情况应该被判无解本质上是因为，有两个平行但反向的向量，且它们互相在对方的右边（此处默认一个向量左边的半平面是我们要取的）

如何判？
当要加入新的一条直线时，要把队列中每个与前一个向量交点在他右边的向量都踢出队列
所以当加入某一个向量而导致出现这种情况时，队列中其他向量之间的交点必然在他的右边，所以它就已经把它右边的向量都弹掉了，那么与他平行且反向的那一个向量成为现在队列里的唯一一个
于是在把当前的向量加入队列后，就只用判断队尾和队尾的前一个会不会构成这种情况即可

于是就是： 

que[++right]=a[i];
if(abs(cross(que[right].way,que[right-1].way))<=eps){//平行
    if(onRight(que[right],que[right-1].p)&&dot(que[right].way,que[right-1].way)<=-eps) return 0;
    right--;
    if(!onRight(que[right],a[i].p)) que[right]=a[i];
}

大概就是叉乘判平行，点乘判夹角大于 90 度，于是就得出了反向

数据比较水，建议去这两题进一步验证一下板子的正确性：POJ2451 Uyuw's Concert 和 POJ1279 Art Gallery

完整代码： 

#define N 100006
#define eps 1e-13
inline double abs(const double &a){return a>0?a:-a;}
struct Vector{
    double x,y;
    inline double len(){return std::sqrt(x*x+y*y);}
    inline void operator += (const Vector &a){x+=a.x;y+=a.y;}
    inline void operator -= (const Vector &a){x-=a.x;y-=a.y;}
    inline void operator *= (const double &a){x*=a;y*=a;}
    inline void operator /= (const double &a){x/=a;y/=a;}
};
inline Vector operator + (const Vector &a,const Vector &b){return (Vector){a.x+b.x,a.y+b.y};}
inline Vector operator - (const Vector &a,const Vector &b){return (Vector){a.x-b.x,a.y-b.y};}
inline Vector operator * (const Vector &a,const double &b){return (Vector){a.x*b,a.y*b};}
inline Vector operator / (const Vector &a,const double &b){return (Vector){a.x/b,a.y/b};}
inline double dot(const Vector &a,const Vector &b){return a.x*b.x+a.y*b.y;}
inline double cross(const Vector &a,const Vector &b){return a.x*b.y-a.y*b.x;}
struct Line{
    Vector p,way;
    double ang;
    inline void makeLine(const Vector &a,const Vector &b){p=a;way=b;ang=atan2(b.y,b.x);}
};
inline int onRight(const Line &a,const Vector &b){return cross(a.way,b-a.p)<=-eps;}
inline int cmp(const Line &a,const Line &b){return a.ang<b.ang;} 
inline Vector intersect(const Line &a,const Line &b){
    double x=cross(b.way,a.p-b.p)/cross(a.way,b.way);
    return a.p+a.way*x;
}
inline double polygonArea(int n,Vector *a){
    double S=0;
    for(reg int i=1;i<n;i++) S+=cross(a[i],a[i+1]);
    S+=cross(a[n],a[1]);
    return S/2;
}
int left,right;
Line que[N];
inline int halfPlane(int n,Line *a,Vector *p){
    std::sort(a+1,a+1+n,cmp);
    left=right=0;que[0]=a[1];
    for(reg int i=2;i<=n;i++){
        while(left<right&&onRight(a[i],p[right])) right--;
        while(left<right&&onRight(a[i],p[left+1])) left++;
        que[++right]=a[i];
        if(abs(cross(que[right].way,que[right-1].way))<=eps){//平行
            if(onRight(que[right],que[right-1].p)&&dot(que[right].way,que[right-1].way)<=-eps) return 0;
            right--;
            if(!onRight(que[right],a[i].p)) que[right]=a[i];
        }
        if(left<right) p[right]=intersect(que[right],que[right-1]);
    }
    while(left<right&&onRight(que[left],p[right])) right--;
    if(right-left<=1) return 0;
    p[left]=intersect(que[left],que[right]);
    return 1;
}
Vector p[N],in[N];
Line a[N];
int main(){
    int n=read(),o=0;
    while(n--){
        int m=read();
        for(reg int i=1;i<=m;i++) in[i].x=read(),in[i].y=read();
        for(reg int i=1;i<m;i++) a[++o].makeLine(in[i],in[i+1]-in[i]);
        a[++o].makeLine(in[m],in[1]-in[m]);
    }
    if(!halfPlane(o,a,p)) puts("0.000");
    else printf("%.3lf\n",polygonArea(right-left+1,p+left-1));
    return 0;
}