网址链接：http://acm.hdu.edu.cn/showproblem.php?pid=1255
题目大意：给出n个矩形的左下角和右上角的坐标，n小于1000，坐标是浮点型的。求解至少被覆盖2次的面积。
解题思路：这个题目是很明显的线段树，但是有几个难点在这里。
1.这个题目需要离散化处理，因为坐标是浮点型的，我们建树的时候需要的是整型的坐标。
2.如何求覆盖2次矩形的面积。这里用到了一些技巧。我们给每条线段定义一个变量cover，表示该线段被覆盖的次数，当插入的线段是下面的边的时候，cover+1，当插入的边是上面的边的时候，cover-1。如果cover>=2，则说明该线段被覆盖了超过2次，就出现了我们需要的面积并。
总结一下，就是：离散化+线段树
下面是我的代码，跑了1000ms左右，速度有点慢。大牛可以跑200ms
源代码：
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
using namespace std;
#define N 2000
int n;
double SS; //要求的面积
double t1[N*4]; //原始记录的x坐标
int cnt; //去重之后数组的个数
double t2[N*4]; //去重之后的x坐标
int hash(double key) //二分hash查找
{
int front,rear,mid;
front=1; rear=cnt;
while(front<rear)
{
mid=(front+rear)/2;
if(t2[mid]==key) return mid;
if(t2[mid]>key) rear=mid-1;
else if(t2[mid]<key) front=mid+1;
}
return front;
}
struct node2 //最终需要插入的线段结构体
{
double x1,x2;
int l,r; //离散化之后的x坐标
double y;
int cover; //下边为1，上边为-1
}segment[N*4];
struct node //线段树
{
int l,r; //离散化之后，x轴方向上的左右端点,主要是依靠x轴来建树
double len; //线段树的真实宽度
double y;
int cover; //表示线段被覆盖的次数,被覆盖两次及以上的时候有面积并
int mid()
{
return (l+r)/2;
}
}s[N*4];
bool cmp(node2 a,node2 b) //对于需要插入的线段结构体，直接按照y排序
{
return a.y<b.y;
}
void build(int step,int l,int r)
{
s[step].l=l; s[step].r=r; s[step].len=t2[r]-t2[l];
s[step].y=0;
s[step].cover=0; //开始默认的都是上面的边
if(s[step].r-s[step].l==1) return; //叶子节点的区间大小为1，不是为0
build(step*2,l,s[step].mid());
build(step*2+1,s[step].mid(),r);
return;
}
void update(int step,int l,int r,double y,int cover)
{
if(s[step].l==l && s[step].r==r && s[step].cover!=-1)
{
if(s[step].cover>=2) //该线段已经覆盖2次了,出现了覆盖2次的面积
{
SS+=s[step].len*(y-s[step].y);
}
s[step].cover+=cover;
s[step].y=y;
return;
}
if(s[step].cover>-1)
//将父亲节点的性质传递给孩子节点,这个地方必须是>-1，否则过不了
{
s[step*2].cover=s[step*2+1].cover=s[step].cover;
s[step*2].y=s[step*2+1].y=s[step].y;
}
s[step].cover=-1; //该区间存在不同的覆盖值或者不同的y值
if(r<=s[step].mid())
{
update(step*2,l,r,y,cover);
}
else if(l>=s[step].mid())
{
update(step*2+1,l,r,y,cover);
}
else
{
update(step*2,l,s[step].mid(),y,cover);
update(step*2+1,s[step].mid(),r,y,cover);
}
//将孩子节点的性质传递给父亲节点
if(s[step*2].cover==s[step*2+1].cover && s[step*2].y==s[step*2+1].y)
{
s[step].cover=s[step*2].cover;
s[step].y=s[step*2].y;
}
return;
}
int main()
{
int cs,i;
double x1,y1,x2,y2;
scanf("%d",&cs);
while(cs--)
{
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
t1[i*2]=x1; t1[i*2+1]=x2;
segment[i*2].x1=x1; segment[i*2].x2=x2;
segment[i*2].y=y1; segment[i*2].cover=1; //下边的标记为1
segment[i*2+1].x1=x1; segment[i*2+1].x2=x2;
segment[i*2+1].y=y2; segment[i*2+1].cover=-1; //上边的标记为-1
}
sort(t1,t1+2*n);
t2[1]=t1[0]; cnt=1;
for(i=1;i<n*2;i++)
{
if(t1[i]!=t1[i-1]) //去重操作
{
t2[++cnt]=t1[i];
}
}
sort(t2+1,t2+cnt+1);
for(i=0;i<2*n;i++)
{
segment[i].l=hash(segment[i].x1);
segment[i].r=hash(segment[i].x2);
}
build(1,1,cnt); //建树
SS=0;
sort(segment,segment+2*n,cmp); //将需要插入的线段根据y坐标进行排序
for(i=0;i<2*n;i++)
{
update(1,segment[i].l,segment[i].r,segment[i].y,segment[i].cover);
}
printf("%.2lf\n",SS);
}
return 0;
}