链接：线段树求矩形面积并 扫描线+离散化
1、给定平面上若干矩形,求出被这些矩形覆盖过至少两次的区域的面积.
2、看完线段树求矩形面积并 的方法后，再看这题，求的是矩形面积交，类同。
求面积时，用被覆盖2次以上的那一段乘以扫描线的距离即可，具体实现见代码。
3、
/*
HDU 1255 覆盖的面积
求矩形面积交（离散化+线段树）
给定一些矩形
求被这些矩形覆盖过至少两次的区域的面积 这里的方法是：线段树求矩形面积交 扫描线+离散化
左右扫描（x轴扫描），把y轴上的线段离散化
*/
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std; const int MAXN=; struct Node
{
int l,r;//离散化后的y值
double lf,rf;//原来的y值，lf代表l原来的y值，rf代表r原来的y值
int cnt;//当前段被覆盖过几次
double lenOnce;//当前段中覆盖一次以上的长度
double lenTwice;//当前段中覆盖两次以上的长度
} segTree[MAXN*];
struct Line
{
double x;//也就是对应的扫描线x坐标
double y1,y2;//线段的端点坐标
double f;//1表示一个矩形左边的边，-1表示右边的边
} line[MAXN]; double y[MAXN]; bool cmp(Line a,Line b)
{
return a.x<b.x;
} void Build(int i,int l,int r)
{
segTree[i].l=l;
segTree[i].r=r;
segTree[i].lenOnce=;
segTree[i].lenTwice=;
segTree[i].lf=y[l];
segTree[i].rf=y[r];
if(l+==r)return;
int mid=(l+r)>>;
Build(i<<,l,mid);
Build((i<<)|,mid,r);
}
void calen(int i)
{
if(segTree[i].cnt>=)//被线段覆盖次数>=2
{
segTree[i].lenOnce=segTree[i].rf-segTree[i].lf;
segTree[i].lenTwice=segTree[i].rf-segTree[i].lf;
return;
}
else if(segTree[i].cnt==)//被线段覆盖次数==1
{
segTree[i].lenOnce=segTree[i].rf-segTree[i].lf; if(segTree[i].l+==segTree[i].r)segTree[i].lenTwice=;//当是叶子节点时
else segTree[i].lenTwice=segTree[i<<].lenOnce+segTree[(i<<)|].lenOnce;
//因为当前线段被覆盖过1次，所以覆盖2次以上的长度是其左右孩子的覆盖1次以上的长度的和
}
else//被线段覆盖次数==0
{
if(segTree[i].l+==segTree[i].r)//当是叶子节点时
{
segTree[i].lenOnce=segTree[i].lenTwice=;
}
else
{//因为当前节点被覆盖次数为0，所以lenOnce和lenTwice的值由左右孩子决定
segTree[i].lenOnce=segTree[i<<].lenOnce+segTree[(i<<)|].lenOnce;
segTree[i].lenTwice=segTree[i<<].lenTwice+segTree[(i<<)|].lenTwice;
}
}
}
void update(int i,Line e)
{
if(e.y1==segTree[i].lf&&segTree[i].rf==e.y2)
{
segTree[i].cnt+=e.f;
calen(i);//更新当前节点信息
return;
} if(e.y2<=segTree[i<<].rf) update(i<<,e);
else if(e.y1>=segTree[(i<<)|].lf) update((i<<)|,e);
else
{
Line temp=e;
temp.y2=segTree[i<<].rf;
update(i<<,temp);
temp=e;
temp.y1=segTree[(i<<)|].lf;
update((i<<)|,temp);
}
calen(i);//更新当前节点信息
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int T;
int n;
double x1,y1,x2,y2;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
int t=;
for(int i=; i<=n; i++)
{
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); //这里题目描述有问题？左下角和右上角
line[t].y1=y1;
line[t].y2=y2;
line[t].x=x1;
line[t].f=;//左边的边
y[t]=y1;//y坐标离散化（下端点）
t++; line[t].y1=y1;
line[t].y2=y2;
line[t].x=x2;
line[t].f=-;//右边的边
y[t]=y2;//y坐标离散化（上端点）
t++;
}
sort(line+,line+t,cmp);//线段按x的值升序排序
sort(y+,y+t);//y坐标从小下到大排序
Build(,,t-);//用离散化后的y值（也就是t）建立线段树 update(,line[]);//从第一条扫描线向右扫描
double ans=;
for(int i=; i<t; i++)
{
ans+=segTree[].lenTwice*(line[i].x-line[i-].x);
update(,line[i]);
}
printf("%.2lf\n",ans);
}
return ;
}