半平面

定义

平面的一半(一直线将平面分成两部分,每个部分称之为半平面).

表示

\(ax+by+c\;\geq\;0,ax+by+c<0\).

半平面交

半平面的交集,即不等式组的解集.可用于解决多边形核的问题.

实现

将半平面按极角排序(靠近法向量方向的半平面更小)
双端队列维护半平面交:顺序加入半平面,当队尾的2个半平面的交点在当前半平面外，删除队尾的半平面;当队头的2个半平面的交点在当前半平面外，删除队头的半平面.
\(P.S.\)形如\(ax+by+c\;\geq\;0\)的方程组的解\(A(x,y)\)满足条件\(\overrightarrow{BA}\;\times\;\overrightarrow{BC}\;\geq\;0(B,C\;\in\;ax+by+c=0)\)(\(ax+by+c<0\)反之)

typedef long double ld;
struct point{
    ld x,y;
}p[N];
struct line{
    point s,e;ld an;
}a[N],q[N];
int n,m,h,t;
inline point dec(point x,point y){
    return (point){x.x-y.x,x.y-y.y};
}
inline ld mult(point x,point y){
    return x.x*y.y-x.y*y.x;
}
inline bool cmp(line x,line y){
    if(x.an==y.an) return mult(dec(x.e,x.s),dec(y.s,x.s))>0;
    return x.an0;
}
inline bool hpi(int k){
    for(int i=1;i<=n;++i) 
        a[i].an=atan2(a[i].e.y-a[i].s.y,a[i].e.x-a[i].s.x);
    sort(a+1,a+1+n,cmp);
    h=1;t=0;
    for(int i=1;i<=n;++i){
        while(h=3;
}

推荐

http://www.cnblogs.com/ka200812/archive/2012/01/20/2328316.html
http://blog.csdn.net/non_cease/article/details/7796834