覆盖的面积
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Problem Description
给定平面上若干矩形,求出被这些矩形覆盖过至少两次的区域的面积.
Input
输入数据的第一行是一个正整数T(1<=T<=100),代表测试数据的数量.每个测试数据的第一行是一个正整数N(1<=N<=1000),代表矩形的数量,然后是N行数据,每一行包含四个浮点数,代表平面上的一个矩形的左上角坐标和右下角坐标,矩形的上下边和X轴平行,左右边和Y轴平行.坐标的范围从0到100000.
注意:本题的输入数据较多,推荐使用scanf读入数据.
Output
对于每组测试数据,请计算出被这些矩形覆盖过至少两次的区域的面积.结果保留两位小数.
Sample Input
2 5 1 1 4 2 1 3 3 7 2 1.5 5 4.5 3.5 1.25 7.5 4 6 3 10 7 3 0 0 1 1 1 0 2 1 2 0 3 1
Sample Output
7.63 0.00
思路:浮点数先要离散化;然后把矩形分成两条边,上边和下边,对横轴建树,然后从下到上扫描上去，进行线段树操作
解题：线段树+扫描线
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
#define maxn 1111
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define Min(a,b) (a<b?a:b)
#define Max(a,b) (a>b?a:b)
struct Node{
double l,r,h;
int flag;
}num[maxn<<1];
double Hash[maxn<<1];
int Mi[maxn<<3],Ma[maxn<<3];
int lazy[maxn<<3];
bool operator <(Node a,Node b)
{
return a.h<b.h;
}
int Bin(int star,int las,double x)
{
int m;
while(star<=las)
{
m=(star+las)>>1;
if(fabs(Hash[m]-x)<1e-10)
return m;
if(Hash[m]>x)
las=m-1;
else
star=m+1;
}
return -1;
}
void PushDown(int rt)
{
lazy[rt<<1]+=lazy[rt];
lazy[rt<<1|1]+=lazy[rt];
Mi[rt<<1]+=lazy[rt]; Ma[rt<<1]+=lazy[rt]; Mi[rt<<1|1]+=lazy[rt]; Ma[rt<<1|1]+=lazy[rt];
lazy[rt]=0;
}
void PushUp(int rt)
{
Mi[rt]=Min(Mi[rt<<1],Mi[rt<<1|1]);
Ma[rt]=Max(Ma[rt<<1],Ma[rt<<1|1]);
}
void build(int l,int r,int rt)
{
Mi[rt]=0;
Ma[rt]=0;
lazy[rt]=0;
if(l==r)
return ;
int m=(l+r)>>1;
build(lson);
build(rson);
}
void updata(int l,int r,int rt,int L,int R,int flag)
{
if(l>=L && r<=R)
{
lazy[rt]+=flag;
Mi[rt]+=flag; Ma[rt]+=flag;
return ;
}
PushDown(rt);
int m=(l+r)>>1;
if(L<=m)
updata(lson,L,R,flag);
if(R>m)
updata(rson,L,R,flag);
PushUp(rt);
}
double query(int l,int r,int rt)
{
if(Mi[rt]>1)
return Hash[r+1]-Hash[l];
if(Ma[rt]<=1)
return 0;
PushDown(rt);
int m=(l+r)>>1;
double s=query(lson)+query(rson);
PushUp(rt);
return s;
}
int main()
{
int n;
int i,cnt,t=1,T;
double x1,x2,y1,y2;
double sum;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
Hash[i*2]=x1; Hash[i*2+1]=x2;
num[i*2].l=x1; num[i*2].r=x2; num[i*2].h=y1; num[i*2].flag=1;
num[i*2+1].l=x1; num[i*2+1].r=x2; num[i*2+1].h=y2; num[i*2+1].flag=-1;
}
sort(Hash,Hash+2*n);
sort(num,num+2*n);
for(i=1,cnt=0;i<2*n;i++)
if(fabs(Hash[i]-Hash[cnt])>1e-10)
Hash[++cnt]=Hash[i];
build(0,cnt,1);
sum=0.0;
for(i=0;i<2*n;i++)
{
updata(0,cnt,1,Bin(0,cnt,num[i].l),Bin(0,cnt,num[i].r)-1,num[i].flag);
sum+=query(0,cnt,1)*(num[i+1].h-num[i].h);
}
printf("%.2lf\n",sum);
}
return 0;
}