覆蓋的面積
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1415 Accepted Submission(s): 677
Problem Description
給定平面上若干矩形,求出被這些矩形覆蓋過至少兩次的區(qū)域的面積.


Input
輸入數(shù)據(jù)的第一行是一個正整數(shù)T(1<=T<=100),代表測試數(shù)據(jù)的數(shù)量.每個測試數(shù)據(jù)的第一行是一個正整數(shù)N(1<=N<=1000),代表矩形的數(shù)量,然后是N行數(shù)據(jù),每一行包含四個浮點數(shù),代表平面上的一個矩形的左上角坐標和右下角坐標,矩形的上下邊和X軸平行,左右邊和Y軸平行.坐標的范圍從0到100000.
注意:本題的輸入數(shù)據(jù)較多,推薦使用scanf讀入數(shù)據(jù).
注意:本題的輸入數(shù)據(jù)較多,推薦使用scanf讀入數(shù)據(jù).
Output
對于每組測試數(shù)據(jù),請計算出被這些矩形覆蓋過至少兩次的區(qū)域的面積.結(jié)果保留兩位小數(shù).
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
Author
Ignatius.L & weigang Lee
Recommend
Ignatius.L
/*
HDU 1255 覆蓋的面積
求矩形交的面積(線段樹+離散化)
給定一些矩形
被這些矩形覆蓋過至少兩次的區(qū)域的面積
*/
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 2010
struct Node
{
int l,r;//線段樹的左右整點
int c;//c用來記錄重疊情況
double lf,rf;//
//rf,lf分別是對應(yīng)的左右真實的浮點數(shù)端點
double cnt,more;//cnt是值被覆蓋一次以上的長度,more值被覆蓋兩次以上的長度
}segTree[MAXN*3];
struct Line
{
double x,y1,y2;
int f;
}line[MAXN];
//把一段段平行于y軸的線段表示成數(shù)組 ,
//x是線段的x坐標,y1,y2線段對應(yīng)的下端點和上端點的坐標
//一個矩形 ,左邊的那條邊f(xié)為1,右邊的為-1,
//用來記錄重疊情況,可以根據(jù)這個來計算,nod節(jié)點中的c
bool cmp(Line a,Line b)//sort排序的函數(shù)
{
return a.x < b.x;
}
double y[MAXN];//記錄y坐標的數(shù)組
void Build(int t,int l,int r)//構(gòu)造線段樹
{
segTree[t].l=l;segTree[t].r=r;
segTree[t].cnt=segTree[t].c=0;
segTree[t].lf=y[l];
segTree[t].rf=y[r];
if(l+1==r) return;
int mid=(l+r)>>1;
Build(t<<1,l,mid);
Build(t<<1|1,mid,r);//遞歸構(gòu)造
}
void calen(int t)//計算長度
{
if(segTree[t].c>=2)
{
segTree[t].more=segTree[t].cnt=segTree[t].rf-segTree[t].lf;
return;
}
else if(segTree[t].c==1)
{
segTree[t].cnt=segTree[t].rf-segTree[t].lf;
if(segTree[t].l+1==segTree[t].r) segTree[t].more=0;
else segTree[t].more=segTree[t<<1].cnt+segTree[t<<1|1].cnt;
}
else
{
if(segTree[t].l+1==segTree[t].r) segTree[t].more=segTree[t].cnt=0;
else
{
segTree[t].cnt=segTree[t<<1].cnt+segTree[t<<1|1].cnt;
segTree[t].more=segTree[t<<1].more+segTree[t<<1|1].more;
}
}
}
void update(int t,Line e)//加入線段e,后更新線段樹
{
if(e.y1==segTree[t].lf&&e.y2==segTree[t].rf)
{
segTree[t].c+=e.f;
calen(t);
return;
}
if(e.y2<=segTree[t<<1].rf) update(t<<1,e);
else if(e.y1>=segTree[t<<1|1].lf) update(t<<1|1,e);
else
{
Line tmp=e;
tmp.y2=segTree[t<<1].rf;
update(t<<1,tmp);
tmp=e;
tmp.y1=segTree[t<<1|1].lf;
update(t<<1|1,tmp);
}
calen(t);
}
int main()
{
int i,n,t,T;
double x1,y1,x2,y2;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
t=1;
for(i=1;i<=n;i++)
{
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
line[t].x=x1;
line[t].y1=y1;
line[t].y2=y2;
line[t].f=1;
y[t]=y1;
t++;
line[t].x=x2;
line[t].y1=y1;
line[t].y2=y2;
line[t].f=-1;
y[t]=y2;
t++;
}
sort(line+1,line+t,cmp);
sort(y+1,y+t);
Build(1,1,t-1);
update(1,line[1]);
double res=0;
for(i=2;i<t;i++)
{
res+=segTree[1].more*(line[i].x-line[i-1].x);
update(1,line[i]);
}
printf("%.2lf\n",res);
}
return 0;
}
文章來源:http://www.cnblogs.com/kuangbin/archive/2011/08/16/2140779.html

