覆盖的面积
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