poj1151 hdu1542 wikioi3044 Atlantis 矩形面積求并

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 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

2
10 10 20 20
15 15 25 25.5
0      

Sample Output

Test case #1
Total explored area: 180.00      

題目大意：給定每個矩形的對角線的兩個端點，讓你求這些矩形的面積的并集，即重疊的不能重複計算

題目分析：這題就是典型的線段樹求面積并

離散化：對所有節點的Y進行升序排序，然後以Y的位置建樹，就是指，線上段樹裡面，左右節點的實際意義就是指這個線段在Y的升序數組裡的位置，但是我們把lf,rf指派為這個線段左右端點的具體值，這就是離散化

建樹的細節：樹的每個節點有lf,rf,cover,lenth，分别指這個節點所表示的線段的左端點，右端點，被覆寫的次數（在這裡覆寫的次數是為了區分重疊矩形的情況下，高度的正确存取，因為一個矩形對Y軸的覆寫是以他的左邊開始，右邊結束的，是以當插入左邊的時候，我們把cover+1，右邊的時候把cover-1，說明這個矩形對Y的覆寫已經結束，計算下一個矩形時，不會錯誤的把我這個矩形的高度當作下一個矩形的高度），lenth指這個區間被矩形覆寫的長度即矩形的實際高度；插入的時候，先把存放節點的數組，對X進行升序排序，然後順次插入，分别計算

#include <stdio.h>
#include <algorithm>
using namespace std;

double x1,y1,x2,y2,ym[1111];
 
struct tree
{
    double lf,rf,lenth;
    int cover;
}s[4444];						//樹節點定義
 
struct node
{
    double x,y1,y2;
    int flag;
}t[4444];						//存放矩形左，右邊的節點
 
int cmp1(double x,double y)
{
    return x < y;
}
 
int cmp2(node a,node b)
{
    return a.x < b.x;
}
 
void len(int n)
{
    if(s[n].cover>0)
        s[n].lenth=s[n].rf-s[n].lf;
    else
        s[n].lenth=s[2*n+1].lenth+s[2*n].lenth;
}
 
int Build(int x,int y,int num)
{
    s[num].lf=ym[x];
    s[num].rf=ym[y];
    s[num].lenth=s[num].cover=0;
    if(x+1==y)	return 0;
    int mid=(x+y)/2;
    Build(x,mid,num+num);
    Build(mid,y,num+num+1);
}
 
int Update(int num,node n)
{
    if(s[num].lf==n.y1 && s[num].rf==n.y2)
	{
        s[num].cover+=n.flag;
        len(num);
        return 0;
    }
    if(n.y1>=s[num+num].rf)	Update(num+num+1,n);
    else if(n.y2<=s[num+num+1].lf)	Update(num+num,n);
    else
	{
        node vs=n;
        vs.y2=s[num+num].rf;
        Update(num+num,vs);
        vs=n;
        vs.y1=s[num+num+1].lf;
        Update(num+num+1,vs);
    }
    len(num);		//往上更新線段被覆寫的實際長度,如果節點的cover>0,
			 		//該區間節點的被覆寫就是區間的整體程度;
			 		//否則,該區間節點的被覆寫等于左右節點被覆寫長度的和
}
 
int main()
{
    int cas,i,j,k=1;
    double sum;
    while(scanf("%d",&cas) && cas)
	{
        for(j=i=1;i<=cas;i++,j+=2)
		{
            scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
            ym[j]=y1;
            t[j].x=x1;
            t[j].y1=y1;
            t[j].y2=y2;
            t[j].flag=1;
            ym[j+1]=y2;
            t[j+1].x=x2;
            t[j+1].y1=y1;
            t[j+1].y2=y2;
            t[j+1].flag=-1;
        }
        sort(ym+1,ym+j,cmp1);
        sort(t+1,t+j,cmp2);
        Build(1,j-1,1);
        Update(1,t[1]);
        sum=0;
        for(i=2;i<j;i++)
		{
            sum+=(t[i].x-t[i-1].x)*s[1].lenth;//每插入完一個點，就以它後繼的點求面積
            Update(1,t[i]);
        }
        printf("Test case #%d\n",k);
        printf("Total explored area: %.2lf\n\n",sum);
        k++;
    }
    return 0;
}