hdu1542 Atlantis 面积交

Atlantis

Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2868Accepted Submission(s): 1320

Problem Description

There are several ancient Greek texts that contain descriptions of the fabled island Atlantis. Some of these texts even include maps of parts of the island. But unfortunately, these maps describe different regions of Atlantis. Your friend Bill has to know the total area for which maps exist. You (unwisely) volunteered to write a program that calculates this quantity.

Input

The input file consists of several test cases. Each test case starts with a line containing a single integer n (1<=n<=100) of available maps. The n following lines describe one map each. Each of these lines contains four numbers x1;y1;x2;y2 (0<=x1<x2<=100000;
0<=y1<y2<=100000), not necessarily integers. The values (x1; y1) and (x2;y2) are the coordinates of the top-left resp. bottom-right corner of the mapped area.

The input file is terminated by a line containing a single 0. Don’t process it.

Output

For each test case, your program should output one section. The first line of each section must be “Test case #k”, where k is the number of the test case (starting with 1). The second one must be “Total explored area: a”, where a is the total explored area (i.e. the area of the union of all rectangles in this test case), printed exact to two digits to the right of the decimal point.

Output a blank line after each test case.

Sample Input

210 10 20 2015 15 25 25.50

Sample Output

Test case #1Total explored area: 180.00 #include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
using namespace std;
struct Line
{
double h;
double x1;
double x2;
int cover;
}line[6666];
struct NODE
{
int left;
int right;
int cover;
double sum;
}node[6666];
double xx[6666];

int cmp(const void *a,const void *b)
{
return (*(struct Line *)a).h>(*(struct Line *)b).h?1:-1;//从小到大 貌似和sort大小号相反
}
/*bool cmp(struct Line&a,struct Line&b){ //一样的
return a.h<b.h;//从小到大
}*/

void build(int left,int right,int nd)
{
int mid;
node[nd].left=left;
node[nd].right=right;
node[nd].cover=0;
node[nd].sum=0;
if(left==right) return ;
mid=(left+right)/2;
build(left,mid,nd*2);
build(mid+1,right,nd*2+1);
}

int bsearch(int p,int q,double c)
{
while(p<=q){
int mid=(p+q)/2;
if(xx[mid]==c)
return mid;
if(xx[mid]<c)
p=mid+1;
else
q=mid-1;
}
return -1;
}

void update(int ind){//为0的时候要分为叶子节点还是别的节点
if(node[ind].cover){
node[ind].sum=xx[node[ind].right+1]-xx[node[ind].left];//在计算和时，还原点值，所以+1
}else if(node[ind].left==node[ind].right){
node[ind].sum=0;
}
else{
node[ind].sum=node[ind*2].sum+node[ind*2+1].sum;
}
}

void insert(int left,int right,int cover,int nd)
{
if(left==node[nd].left&&right==node[nd].right)
{
node[nd].cover+=cover;
update(nd);
return ;
}
int mid=(node[nd].left+node[nd].right)/2;
if(right<=mid) insert(left,right,cover,nd*2);
else
if(left>mid) insert(left,right,cover,nd*2+1);
else
{
insert(left,mid,cover,nd*2);
insert(mid+1,right,cover,nd*2+1);
}
update(nd);
}

int main()
{
int i,j,n,cnt=0,k;
double ans;
while(scanf("%d",&n)&&n!=0)
{
ans=0;
double x1,x2,y1,y2;
k=0;
for(i=0;i<n;i++)
{
scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
line[k].x1=x1;
line[k].x2=x2;
line[k].h=y1;
line[k].cover=1;
xx[k]=x1;
k++;
line[k].x1=x1;
line[k].x2=x2;
line[k].cover=-1;
line[k].h=y2;
xx[k]=x2;
k++;
}
sort(xx,xx+k);
qsort(line,k,sizeof(line[0]),cmp);
// sort(line,line+k,cmp);
j=k;k=1;//这里是 1啊 因为这里 RE了10边啊！！！！
for(i=1;i<j;i++)
{
if(xx[i]!=xx[i-1])
xx[k++]=xx[i];
}
sort(xx,xx+k);
k--;
build(0,k,1);
for(i=0;i<j-1;i++)//是j-1啊
{
int left,right;
left=bsearch(0,k,line[i].x1);
right=bsearch(0,k,line[i].x2)-1;
if(right<left){//两个点重复时，特殊处理！
ans+=node[1].sum*(line[i+1].h-line[i].h);
continue;
}
insert(left,right,line[i].cover,1);
ans+=node[1].sum*(line[i+1].h-line[i].h);//从这里也应该看出上面是j-1
}
printf("Test case #%d\n",++cnt);
printf("Total explored area: %.2lf\n\n",ans);
}
return 0;
}