【无聊放个模板系列】 半平面交

求半平面交的面积

 

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define Maxn 1100

struct P {double x,y;};
struct L {P a,b;double slop;}l[Maxn];
//半平面只方向向量a->b的左部分
//slop 极角
int cnt;

P operator - (P x,P y)
{
    P tt;
    tt.x=x.x-y.x;
    tt.y=x.y-y.y;
    return tt;
}

P operator + (P x,P y)
{
    P tt;
    tt.x=x.x+y.x;
    tt.y=x.y+y.y;
    return tt;
}

double Dot(P x,P y) {return x.x*y.x+x.y*y.y;}
double Cross(P x,P y) {return x.x*y.y-x.y*y.x;}

bool operator < (L a,L b)
{
    if(a.slop!=b.slop)return a.slop<b.slop;
    return Cross(a.b-a.a,b.b-a.a)>0;
}

P operator * (P X,double y)
{
    P tt;
    tt.x=X.x*y;
    tt.y=X.y*y;
    return tt;
}

P a[Maxn];
L q[Maxn];
int tot;

P inter(L a,L b)
{
    P X=a.a-a.b,Y=b.a-b.b,nw;
    double tt;
    nw=b.a-a.a;
    tt=Cross(nw,X)/Cross(X,Y);
    P ans=b.a+Y*tt;
    return ans;
}

bool jud(L a,L b,L c)
{
    P p=inter(a,b);
    return Cross(c.b-c.a,p-c.a)<0;
}

void opp()
{
    for(int i=1;i<=cnt;i++)
    {
        printf("%.2lf %.2lf %.2lf %.2lf = %.2lf \n",l[i].a.x,l[i].a.y,l[i].b.x,l[i].b.y,l[i].slop);
    }
    printf("\n");
}

void output()
{
    for(int i=1;i<=tot;i++) printf("%2lf %.2lf\n",a[i].x,a[i].y);
    printf("\n");
}

void op(int L,int R)
{
    for(int i=L;i<=R;i++)
        printf("%lf %lf %lf %lf\n",l[i].a.x,l[i].a.y,l[i].b.x,l[i].b.y);
    printf("\n");
}

void ffind()
{
    for(int i=1;i<=cnt;i++)
      l[i].slop=atan2(l[i].b.y-l[i].a.y,l[i].b.x-l[i].a.x);
    sort(l+1,l+1+cnt);
    
    // opp();
    
    int L=1,R=0;
    //去重？
    tot=0;
    for(int i=1;i<=cnt;i++)
    {
        if(l[i].slop!=l[i-1].slop) tot++;
        l[tot]=l[i];
    }
    cnt=tot;tot=0;
    // opp();
    q[++R]=l[1];q[++R]=l[2];
    for(int i=3;i<=cnt;i++)
    {
        while(L<R&&jud(q[R-1],q[R],l[i])) R--;
        while(L<R&&jud(q[L+1],q[L],l[i])) L++;
        q[++R]=l[i];
        // op(L,R);
    }
	if(L<R&&jud(q[R-1],q[R],q[L])) R--;
        op(L,R);
    q[R+1]=q[L];
    for(int i=L;i<=R;i++)
      a[++tot]=inter(q[i],q[i+1]);
  // output();
}

void init()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lf%lf%lf%lf\n",&l[i].a.x,&l[i].a.y,&l[i].b.x,&l[i].b.y);
    }
    cnt=n;
}

void get_area()
{
    double ans=0;
    for(int i=1;i<tot;i++)
    {
        ans+=Cross(a[i],a[i+1]);
    }
    ans+=Cross(a[tot],a[1]);
    if(tot<3) ans=0;
    printf("%.3lf\n",ans/2);
}

int main()
{
    init();
    ffind();
    get_area();
    return 0;
}

　　

 

没有删调试的。

输入半平面，输出面积。

 

样例：

6
4 5 2 0
9 2 5 6
3 1 9 5
5 1 7 5
8 2 9 4
5 7 3 5

 

输出：

10.459

 

2016-12-25 14:39:14