标签：扫描线
题目
Description
给出n个三角形，求它们并的面积。
Input
第一行为n(N < = 100)， 即三角形的个数 以下n行，每行6个整数x1, y1, x2, y2, x3, y3，代表三角形的顶点坐标。坐标均为不超过10 ^ 6的实数，输入数据保留1位小数
Output
输出并的面积u, 保留两位小数
Sample Input
2
0.0 0.0 2.0 0.0 1.0 1.0
1.0 0.0 3.0 0.0 2.0 1.0
Sample Output
1.75
分析
对于每个三角形的三条边，将它们的交点求出来
对每个交点和三角形顶点的x坐标排序，以这些x坐标划分区域
显然每个区域为一个或多个的三角形或梯形组成
对每块图形求中位线并累和计算面积
code
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read(){
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
//**********head by yjjr**********
const int maxn=306;
const double inf=2e7,eps=1e-8;
double x[maxn*maxn],ans;
int n,cnt=0;
struct P{
double x,y;
P(){x=y=0.0;}
P(double _x,double _y){x=_x,y=_y;}
}tri[maxn][4],seg[maxn];
inline P operator + (P a,P b){return P(a.x+b.x,a.y+b.y);}
inline P operator - (P a,P b){return P(a.x-b.x,a.y-b.y);}
inline P operator * (P a,double val){return P(a.x*val,a.y*val);}
inline P operator / (P a,double val){return P(a.x/val,a.y/val);}
inline double operator * (P a,P b){return a.x*b.x+a.y*b.y;}
inline bool cmpa(P a,P b){return a.x<b.x;}
inline int sig(double x){if(fabs(x)<eps)return 0;else return x>0?1:-1;}
inline double cross(P a,P b){return a.x*b.y-a.y*b.x;}
inline bool check(P a,P b,P p,P q){
int d1=sig(cross(b-a,p-a)),d2=sig(cross(b-a,q-a)),d3=sig(cross(q-p,a-p)),d4=sig(cross(q-p,b-p));
return d1*d2<0&&d3*d4<0;
}
inline P getmidline(P a,P b,P p,P q){
double U=cross(p-a,q-p),D=cross(b-a,q-p);
return a+(b-a)*(U/D);
}
inline double cal(double x){
P D(x,-inf),U(x,inf);
int num=0;
rep(i,1,n){
int k=0;double y[2];
rep(j,0,2)
if(check(tri[i][j],tri[i][j+1],D,U))y[k++]=getmidline(tri[i][j],tri[i][j+1],D,U).y;
if(k)seg[num++]=P(min(y[0],y[1]),max(y[0],y[1]));
}
if(num>1)sort(seg,seg+num,cmpa);
double l=-inf,r=-inf,t=0;
rep(i,0,num-1){if(sig(seg[i].x-r)>0)t+=r-l,l=seg[i].x;r=max(r,seg[i].y);}
return t+r-l;
}
int main()
{
n=read();
rep(i,1,n){
rep(j,0,2)scanf("%lf%lf",&tri[i][j].x,&tri[i][j].y);
tri[i][3]=tri[i][0];
}
rep(i,1,n)rep(j,0,2)x[++cnt]=tri[i][j].x;
rep(i,1,n)rep(j,1,i-1)rep(k,0,2)rep(l,0,2)
if(check(tri[i][k],tri[i][k+1],tri[j][l],tri[j][l+1]))
x[++cnt]=getmidline(tri[i][k],tri[i][k+1],tri[j][l],tri[j][l+1]).x;
sort(x+1,x+1+cnt);
rep(i,2,cnt)if(sig(x[i]-x[i-1]))ans+=(x[i]-x[i-1])*cal((x[i]+x[i-1])/2);
printf("%.2lf\n",ans-eps);
return 0;
}
