扫描线
矩形面积并
离散+从左向右扫，这里的线段树是根据lazy来维护sum的。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define x first
#define y second
using namespace std;
const int N = 1e5+10;
typedef pair<int,int> PII;
typedef long long LL;
int n,cnt;
PII l[N],r[N];
LL ans;
vector<int> vy;
struct Line{
int down,up,x,tar;
bool operator < (const Line& X)const{return x<X.x;}
}line[N];
struct Tree{
int l,r;
LL sum,lazy;
void init(int _l,int _r)
{
l=_l,r=_r;
sum=0,lazy=0;
}
}tr[N<<2];
void pushup(int u)
{
if(tr[u].lazy) tr[u].sum=vy[tr[u].r+1]-vy[tr[u].l];
else if(l==r) tr[u].sum=0;
else tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}
void build(int l,int r,int u)
{
tr[u].init(l,r);
if(l==r) return;
int mid=l+r>>1;
build(l,mid,u<<1),build(mid+1,r,u<<1|1);
}
void update(int l,int r,int k,int u)
{
if(tr[u].l>=l&&tr[u].r<=r)
{
tr[u].lazy+=k;
pushup(u);
return;
}
int mid=tr[u].l+tr[u].r>>1;
if(mid>=l) update(l,r,k,u<<1);
if(mid<r) update(l,r,k,u<<1|1);
pushup(u);
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d%d%d%d",&l[i].x,&l[i].y,&r[i].x,&r[i].y);
vy.push_back(l[i].y),vy.push_back(r[i].y);
}
sort(vy.begin(),vy.end());
vy.erase(unique(vy.begin(),vy.end()),vy.end());
for(int i=0;i<n;i++)
{
int down=lower_bound(vy.begin(),vy.end(),l[i].y)-vy.begin();
int up=lower_bound(vy.begin(),vy.end(),r[i].y)-vy.begin();
line[cnt++]=(Line){down,up,l[i].x,1};
line[cnt++]=(Line){down,up,r[i].x,-1};
}
sort(line,line+cnt);
build(0,vy.size()-1,1);
for(int i=0;i<cnt;i++)
{
if(i) ans+=(LL)tr[1].sum*(line[i].x-line[i-1].x);
update(line[i].down,line[i].up-1,line[i].tar,1);
}
printf("%lld",ans);
return 0;
}三角形面积并
二维平面三角形交集，我们可以对每一个横坐标进行剖分，可以发现中间的部分为梯形或平行四边形，但是任然可以用梯形的方式求面积。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define x first
#define y second
using namespace std;
typedef pair<double,double> PDD;
const int N = 110;
const double eps = 1e-8,inf=1e6;
int n;
PDD tr[N][3];
PDD q[N];
int sign(double x)
{
if(fabs(x)<eps) return 0;
return x<0?-1:1;
}
int dcmp(double x,double y)
{
if(fabs(x-y)<eps) return 0;
return x<y?-1:1;
}
PDD operator +(PDD a,PDD b)
{
return {a.x+b.x,a.y+b.y};
}
PDD operator -(PDD a,PDD b)
{
return {a.x-b.x,a.y-b.y};
}
PDD operator *(PDD a,double t)
{
return {a.x*t,a.y*t};
}
double cross(PDD a,PDD b)
{
return a.x*b.y-a.y*b.x;
}
double point(PDD a,PDD b)
{
return a.x*b.x+a.y*b.y;
}
bool on_segment(PDD p,PDD a,PDD b)
{
return sign(point(p-a,p-b))<=0;
}
PDD get_line_intersecion(PDD p,PDD v,PDD q,PDD w)
{
if(!sign(cross(v,w))) return {inf,inf};
auto u=p-q;
double t=cross(w,u)/cross(v,w);
auto o=p+v*t;
if(!on_segment(o,p,p+v)||!on_segment(o,q,q+w))
return {inf,inf};
return o;
}
double line_area(double a,int side)
{
int cnt=0;
for(int i=0;i<n;i++)
{
auto t=tr[i];
if(dcmp(t[0].x,a)>0||dcmp(t[2].x,a)<0) continue;
if(!dcmp(t[0].x,a)&&!dcmp(t[1].x,a))
{
if(side) q[cnt++]={t[0].y,t[1].y};
}
else if(!dcmp(t[2].x,a)&&!dcmp(t[1].x,a))
{
if(!side) q[cnt++]={t[2].y,t[1].y};
}
else{
double d[3];
int u=0;
for(int j=0;j<3;j++)
{
auto o=get_line_intersecion(t[j],t[(j+1)%3]-t[j],{a,-inf},{0,inf*2});
if(dcmp(o.x,inf))
d[u++]=o.y;
}
if(u)
{
sort(d,d+u);
q[cnt++]={d[0],d[u-1]};
}
}
}
if(!cnt) return 0;
for(int i=0;i<cnt;i++)
if(q[i].x>q[i].y)
swap(q[i].x,q[i].y);
sort(q,q+cnt);
double res=0,st=q[0].x,ed=q[0].y;
for(int i=1;i<cnt;i++)
if(q[i].x<ed) ed=max(ed,q[i].y);
else{
res+=ed-st;
st=q[i].x,ed=q[i].y;
}
res+=ed-st;
return res;
}
double range_area(double a,double b)
{
return (line_area(a,1)+line_area(b,0))*(b-a)/2;
}
int main()
{
scanf("%d",&n);
vector<double> xs;
for(int i=0;i<n;i++)
{
for(int j=0;j<3;j++)
{
scanf("%lf%lf",&tr[i][j].x,&tr[i][j].y);
xs.push_back(tr[i][j].x);
}
sort(tr[i],tr[i]+3);
}
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
for(int x=0;x<3;x++)
for(int y=0;y<3;y++)
{
auto o=get_line_intersecion(tr[i][x],tr[i][(x+1)%3]-tr[i][x],tr[j][y],tr[j][(y+1)%3]-tr[j][y]);
if(dcmp(o.x,inf))
xs.push_back(o.x);
}
sort(xs.begin(),xs.end());
double res=0;
for(int i=0;i+1<xs.size();i++)
if(dcmp(xs[i],xs[i+1]))
res+=range_area(xs[i],xs[i+1]);
printf("%.2lf\n",res);
return 0;
}
