求半平面交的面積模闆

題意

在一個有限大（-10 0000<=x,y<=10 0000)的平面坐标系上有n個半平面（注意有限的），每個半平面給出一條有向線段（x1,y1)——>(x2,y2）。

每個半平面的有效區域都是左側。求這n個半平面的交的面積。

題解

半平面交的模闆

以前偷懶，學了個 (n2) ( n 2 ) 的，但是已經忘了啊

于是今天趁沒網學了個 的nlogn 的 n l o g n

模闆調了一個多小時QAQ

現在才會啊

感覺也不難。。

就這樣，存下闆子吧。。

教程我就不寫了

CODE:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const double MAX=;
const int N=;
const double eps=e-;
int n;
struct pnt{double x,y;};
struct qq
{
    pnt x,y;
    double angle;
}s[N];int tot=;
void add (double x1,double y1,double x2,double y2)
{
    tot++;
    s[tot].x.x=x1;
    s[tot].x.y=y1;
    s[tot].y.x=x2;
    s[tot].y.y=y2;
    /*s[tot].x=pnt{x1,y1};
    s[tot].y=pnt{x2,y2};*/
    s[tot].angle=atan2(y2-y1,x2-x1);
}
double mul (pnt x,pnt y,pnt z)
{
    double x1=x.x-z.x,x2=y.x-z.x;
    double y1=x.y-z.y,y2=y.y-z.y;
    return x1*y2-x2*y1;
}
bool cmp (qq x,qq y)
{
    if (abs(x.angle-y.angle)<eps)
        return mul(x.y,y.y,x.x)<-eps;
    return x.angle<y.angle;
}
int q[N];
pnt JD(qq x,qq y)//兩條直線的交點 
{
    double s1=mul(x.y,y.x,x.x);
    double s2=mul(x.y,x.x,y.y);
    pnt xx;
    xx.x=(y.x.x*s2+y.y.x*s1)/(s1+s2);
    xx.y=(y.x.y*s2+y.y.y*s1)/(s1+s2);
    return xx;
}
bool check (qq x,qq a,qq b)//a，b的交點是不是在x的右側 
{
    pnt xx=JD(a,b);
    return mul(x.y,xx,x.x)<-eps;
}
pnt ans[N];
void solve ()
{
    sort(s+,s++tot,cmp);

    n=;
    for (int u=;u<=tot;u++)
        if (abs(s[u].angle-s[n].angle)>eps)
            s[++n]=s[u];
    int st=,ed=;
    q[1]=;q[2]=;
    for (int u=;u<=n;u++)
    {
        while (st<ed&&check(s[u],s[q[ed]],s[q[ed-1]])) ed--;    
        while (st<ed&&check(s[u],s[q[st]],s[q[st+1]])) st++;
        q[++ed]=u;
    }

    while (st<ed&&check(s[q[st]],s[q[ed]],s[q[ed-1]])) ed--;
    while (st<ed&&check(s[q[ed]],s[q[st]],s[q[st+1]])) st++;
    q[++ed]=q[st];
    n=;
    for (int u=st;u<ed;u++)
        ans[++n]=JD(s[q[u]],s[q[u+1]]); 
    /*for (int u=1;u<=n;u++)
        printf("YES:%lf %lf\n",ans[u].x,ans[u].y);*/
}
int main()
{
    scanf("%d",&n);
    for (int u=;u<=n;u++)
    {
        double x1,y1,x2,y2;
        scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
        add(x1,y1,x2,y2);
    }
    add(-MAX,-MAX,MAX,-MAX);
    add(MAX,-MAX,MAX,MAX);
    add(MAX,MAX,-MAX,MAX);
    add(-MAX,MAX,-MAX,-MAX);
    solve();
    if (n<=)
    {
        printf("0.0\n");
        return ;
    }
    double lalal=;
    for (int u=;u<=n;u++)
        lalal=lalal+mul(ans[u],ans[u-],ans[]);
    printf("%.1lf\n",abs(lalal)/);
    return ;
}