Bzoj1845 [cqoi2005] 三角形面积并

三角形求并的面积

Posted by yjjr's blog on March 19, 2018

标签:扫描线

题目

题目传送门

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;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr