hdu 1255 覆蓋的面積 線段樹求面積的交 我感覺有點難啊~~第一次寫這種類型的

覆蓋的面積

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3968 Accepted Submission(s): 1967


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

上博客吧~~我是沒能力講解啊~ http://www.cnblogs.com/ka200812/archive/2011/11/13/2247064.html
代碼：

#include 
#include 

using namespace std ;

double y[2010] ;

struct Line{
	double x,y_up,y_down ;
	int mark;
}line[2010];

struct node{
	double x;
	double y_up,y_down;
	double cover;
	bool isLeaf ;
}st[400100];

void build(int l , int r , int pos)
{
	st[pos].x = -1   ;
	st[pos].y_down = y[l] ;
	st[pos].y_up = y[r] ;
	st[pos].cover = 0 ;
	st[pos].isLeaf = false ;
	if(l+1 == r)
	{
		st[pos].isLeaf = true ;
		return ;
	}
	int mid = (l+r)>>1 ;
	build(l,mid,pos<<1) ;
	build(mid,r,pos<<1|1) ;
}

double insert(double x , double y_down , double y_up , int mark , int pos)
{
	if(st[pos].y_down>=y_up || st[pos].y_up<=y_down)
	{
		return 0 ;
	}
	if(st[pos].isLeaf)
	{
		if(st[pos].cover>1)
		{
			double tempx = st[pos].x ;
			double area = (x-tempx)*(st[pos].y_up-st[pos].y_down) ;
			st[pos].x = x ;
			st[pos].cover += mark ;
			return area ;
		}
		else
		{
			st[pos].cover += mark ;
			st[pos].x = x ;
			return 0 ;
		}
	}
	return insert(x,y_down,y_up,mark,pos<<1)+insert(x,y_down,y_up,mark,pos<<1|1) ;
}
bool cmp(const Line &a , const Line &b)
{
	return a.x