# Bzoj1845 [cqoi2005] 三角形面积并

## 三角形求并的面积

Posted by yjjr's blog on March 19, 2018 1 minutes to read

# 题目

## 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


# 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;
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;
}
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()
{
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;
}