题目描述
逆时针给出n个凸多边形的顶点坐标，求它们交的面积。例如n=2时，两个凸多边形如下图：
则相交部分的面积为5.233。
输入
第一行有一个整数n，表示凸多边形的个数，以下依次描述各个多边形。第i个多边形的第一行包含一个整数mi，表示多边形的边数，以下mi行每行两个整数，逆时针给出各个顶点的坐标。
输出
输出文件仅包含一个实数，表示相交部分的面积，保留三位小数。
样例输入
2
6
-2 0
-1 -2
1 -2
2 0
1 2
-1 2
4
0 -3
1 -1
2 2
-1 0
6
-2 0
-1 -2
1 -2
2 0
1 2
-1 2
4
0 -3
1 -1
2 2
-1 0
样例输出
5.233
提示
100%的数据满足：2<=n<=10，3<=mi<=50，每维坐标为[-1000,1000]内的整数
半平面交模板题，就是求多边形所有边的半平面交。
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const double eps=1e-5;
struct lty
{
double x,y;
lty(double X=0,double Y=0){x=X,y=Y;}
};
struct miku
{
double x,y;
miku(double X=0,double Y=0){x=X,y=Y;}
};
struct line
{
lty s,t;
line(){}
line(lty S,lty T){s=S,t=T;}
};
miku operator -(lty a,lty b)
{
return miku(a.x-b.x,a.y-b.y);
}
miku operator *(miku a,double b)
{
return miku(a.x*b,a.y*b);
}
lty operator +(lty a,miku b)
{
return lty(a.x+b.x,a.y+b.y);
}
double get(miku a,miku b)
{
return a.x*b.y-a.y*b.x;
}
double tan(miku a)
{
return atan2(a.y,a.x);
}
double tan(line a)
{
miku res=a.t-a.s;
return atan2(res.y,res.x);
}
int n,m,k;
int cnt;
line a[100010];
line q[100010];
lty p[100010];
int D(double x)
{
if(fabs(x)<eps)
{
return 0;
}
return x<0?-1:1;
}
double ask(int num)
{
double ans=0;
for(int i=2;i<num;i++)
{
ans+=fabs(get(p[i]-p[1],p[i+1]-p[1]));
}
return ans/2.0;
}
bool cmp(line a,line b)
{
miku v1=a.t-a.s,v2=b.t-b.s;
double s1=tan(v1),s2=tan(v2);
int d=D(s1-s2);
if(!d)
{
return get(v1,b.t-a.s)>0;
}
return d<0;
}
lty find(line a,line b)
{
miku u=a.s-b.s,v=a.t-a.s,w=b.t-b.s;
if(!D(get(v,w)))
{
return a.s;
}
double x=get(w,u)/get(v,w);
return a.s+v*x;
}
bool check(line a,line b,line c)
{
lty e=find(b,c);
int d=D(get(a.t-a.s,e-a.s));
return d>0?false:true;
}
void solve()
{
sort(a+1,a+n+1,cmp);
int l=1,r=0;
int cnt=0;
for(int i=1;i<n;i++)
{
if(!D(tan(a[i])-tan(a[i+1])))
{
continue;
}
a[++cnt]=a[i];
}
a[++cnt]=a[n];
for(int i=1;i<=cnt;i++)
{
while(l<r&&check(a[i],q[r],q[r-1]))
{
r--;
}
while(l<r&&check(a[i],q[l],q[l+1]))
{
l++;
}
q[++r]=a[i];
}
while(l<r&&check(q[l],q[r],q[r-1]))
{
r--;
}
while(l<r&&check(q[r],q[l],q[l+1]))
{
l++;
}
int num=0;
for(int i=l;i<r;i++)
{
p[++num]=find(q[i],q[i+1]);
}
p[++num]=find(q[r],q[l]);
if(num<3)
{
printf("0.000");
return ;
}
printf("%.3f",ask(num));
}
int main()
{
scanf("%d",&k);
while(k--)
{
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
cnt++;
if(i!=1)
{
a[cnt].s=a[cnt-1].t;
}
scanf("%lf%lf",&a[cnt].t.x,&a[cnt].t.y);
}
a[cnt-m+1].s=a[cnt].t;
}
n=cnt;
solve();
}