[POJ2451 Uyuw’s Concert]【例题】【半平面交】

给定一个10000*10000的区域，然后给出一些向量，要找一个最大的区域，区域中的点都满足在这个大区域内，并且对每个向量满足在其左手边。

就是裸的半平面交啊……看了ZZY的论文跟着写WA到半死。后来由叉姐精心指导下，围观了神奇的优化版，不再需要上下凸壳合并T_T(这就是ZZY那算法最容易错的地方了)

记录一下算法的流程：

一开始按atan2来极角排序，极角一样的两个半平面选择那个限制得最紧的那个，其它删掉。

然后就按顺序枚举每一个半平面把它们尝试都交起来，并用一个双端队列保存有效的半平面。

可见如果当前半平面如图所示，那么队列就要pop_back了。这个判定的标准是队尾两个半平面的交点不在当前半平面所需要的平面内。

而如果出现如图的半平面，队列就要pop_front了。这个的判定标准是队头两个半平面的交点在当前半平面所的需求之外。

然后还有一堆疑问。

1、G++ WA C++ AC

2、中间枚举删边时还必须先做pop_back再做pop_front，否则会WA。影响这个只有一种可能，就是队中只剩两个半平面，并且它们的交点在当前半平面的需求之外，先pop_front会是前面的被删掉，而先pop_back会是后面的被删掉。那么围观此图，容易发现pop_back才是正确的。

差不多就这样。

【CODE】

 constdouble eps=1e-9;
inline
int sign(double x){
    if (x<-eps) return -1;
    if (x> eps) return  1;
    return0;
}
struct TPoint{
    double x,y;
    inline
    TPoint operator + (TPoint oth){
        TPoint ret;
        ret.x=x+oth.x;
        ret.y=y+oth.y;
        return ret;
    }
    inline
    TPoint operator – (TPoint oth){
        TPoint ret;
        ret.x=x-oth.x;
        ret.y=y-oth.y;
        return ret;
    }
    inline
    doubleoperator ^ (TPoint oth){
        return x*oth.y-y*oth.x;
    }
};
struct TLine{
    TPoint p1,p2;
    double angle;
};

struct abcLine{
    double a,b,c;
};

inline
abcLine Get_Line(TPoint A,TPoint B){
    abcLine ret;
    ret.a=A.y-B.y;
    ret.b=B.x-A.x;
    ret.c=B.y*A.x-B.x*A.y;
    return ret;
}
inline
TPoint jiao(TLine AA,TLine BB){
    TPoint ret;
    abcLine A=Get_Line(AA.p1,AA.p2);
    abcLine B=Get_Line(BB.p1,BB.p2);
    ret.x=(A.b*B.c-A.c*B.b)/(A.a*B.b-B.a*A.b);
    ret.y=(A.c*B.a-A.a*B.c)/(A.a*B.b-B.a*A.b);
    return ret;
}

deque deque inline
bool cmp(TLine A,TLine B){
    int ret=sign(A.angle-B.angle);
    if (ret>0) returntrue;
    if (ret<0) returnfalse;
    if (sign((B.p2-B.p1)^(A.p1-B.p1))>=0) returntrue;
                                     elsereturnfalse;
}
inline
bool check(TLine p0,TLine p1,TLine p2){
    TPoint cross=jiao(p0,p1);
    return sign((p2.p2-p2.p1)^(cross-p2.p1))>0;
}

void solve(){
    int i;
    for (i=0;i    #define S Q.size()
    Q.clear();
    sort(L.begin(),L.end(),cmp);
    for (i=0;i      if (i==0 || sign(L[i].angle-L[i-1].angle)!=0) Q.push_back(L[i]);
    L=Q; Q.clear();
    for (i=0;i        while (S>=2 && !check(Q[S-2],Q[S-1],L[i])) Q.pop_back();
        while (S>=2 && !check(Q[0],Q[1],L[i]))     Q.pop_front();
        Q.push_back(L[i]);
    }
    while (S>=2 && !check(Q[S-2],Q[S-1],Q[0])) Q.pop_back();
    while (S>=2 && !check(Q[0],Q[1],Q[S-1])) Q.pop_front();
    #undef S
    convex.clear();
    if (Q.size()<2) return;
    for (int i=0;i      convex.push_back(jiao(Q[i],Q[(i+1)%Q.size()]));
}
inline
void add(double x1,double y1,double x2,double y2){
    TLine ret;
    ret.p1.x=x1;
    ret.p1.y=y1;
    ret.p2.x=x2;
    ret.p2.y=y2;
    L.push_back(ret);
}

int main(){
    double x1,y1,x2,y2;
    int n;
    scanf("%d",&n);
    L.clear();
    for (int i=0;i        scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
        add(x1,y1,x2,y2);
    }
    add(    0,    0,10000,    0);
    add(10000,    0,10000,10000);
    add(10000,10000,    0,10000);
    add(0,    10000,    0,    0);
    solve();
    double ans=0;
    if (Q.size()>2){
      for (int i=0;i        ans+=convex[i]^convex[(i+1)%convex.size()];
    }
    ans/=2;
    if (ans<0) ans=-ans;
    printf("%.1lfn",ans);
}