【BZOJ1845】[Cqoi2005] 三角形面积并 几何+扫描线

【BZOJ1845】[Cqoi2005] 三角形面积并

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坐标（注意eps!），然后从左到右扫描每个区域。发现每个区域都可以看成若干个梯形，所以只需要用一条直线去截这些梯形的中间，得到所有梯形的中位线长乘上高度即为答案。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=110;
const double eps=1e-10;
double now,ans;
int n,m,tot,sum;
struct point
{
double x,y;
point(){}
point(double a,double b){x=a,y=b;}
point operator + (point a){return point(x+a.x,y+a.y);}
point operator - (point a){return point(x-a.x,y-a.y);}
double operator * (point a){return x*a.y-y*a.x;}
point operator * (double a){return point(x*a,y*a);}
point operator / (double a){return point(x/a,y/a);}
};
struct line
{
point x,v;
line() {}
line(point a,point b){x=a,v=b;}
}s[310];
struct trangle
{
point a,b,c;
}t[110];
struct node
{
double x;
int v;
}q[210];
double p[100000];
bool cmp(node a,node b)
{
return a.x<b.x;
}
point getpoint(line a,line b)
{
point u=a.x-b.x;
double temp=(b.v*u)/(a.v*b.v);
return a.x+a.v*temp;
}
void calc(line a,line b)
{
if(fabs(a.v*b.v)<eps)return ;
point c=getpoint(a,b);
p[++m]=c.x;
}
int main()
{
scanf("%d",&n);
int i,j;
for(i=1;i<=n;i++)
{
scanf("%lf%lf%lf%lf%lf%lf",&t[i].a.x,&t[i].a.y,&t[i].b.x,&t[i].b.y,&t[i].c.x,&t[i].c.y);
if(t[i].a.x>t[i].b.x)swap(t[i].a,t[i].b);
if(t[i].a.x>t[i].c.x)swap(t[i].a,t[i].c);
if(t[i].b.x>t[i].c.x)swap(t[i].b,t[i].c);
s[i]=line(t[i].a,t[i].b-t[i].a),s[i+n]=line(t[i].a,t[i].c-t[i].a),s[i+n+n]=line(t[i].b,t[i].c-t[i].b);
}
for(i=1;i<=3*n;i++)for(j=i+1;j<=3*n;j++)calc(s[i],s[j]);
sort(p+1,p+m+1);
for(i=1;i<m;i++)
{
if(p[i+1]-p[i]<eps)continue;
now=(p[i]+p[i+1])/2;
for(tot=0,j=1;j<=n;j++)
{
if(now>=t[j].a.x&&now<=t[j].b.x)
{
q[++tot].x=t[j].a.y+(t[j].b.y-t[j].a.y)/(t[j].b.x-t[j].a.x)*(now-t[j].a.x);
q[++tot].x=t[j].a.y+(t[j].c.y-t[j].a.y)/(t[j].c.x-t[j].a.x)*(now-t[j].a.x);
if(q[tot].x<q[tot-1].x)swap(q[tot],q[tot-1]);
q[tot-1].v=1,q[tot].v=-1;
}
if(now>=t[j].b.x&&now<=t[j].c.x)
{
q[++tot].x=t[j].c.y+(t[j].b.y-t[j].c.y)/(t[j].c.x-t[j].b.x)*(t[j].c.x-now);
q[++tot].x=t[j].c.y+(t[j].a.y-t[j].c.y)/(t[j].c.x-t[j].a.x)*(t[j].c.x-now);
if(q[tot].x<q[tot-1].x)swap(q[tot],q[tot-1]);
q[tot-1].v=1,q[tot].v=-1;
}
}
sort(q+1,q+tot+1,cmp);
for(sum=0,j=1;j<=tot;j++)
{
if(sum)ans+=(p[i+1]-p[i])*(q[j].x-q[j-1].x);
sum+=q[j].v;
}
}
printf("%.2lf",ans-eps);
return 0;
}