HDU1255(KB7-O)

覆盖的面积

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

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

Author

Ignatius.L & weigang Lee

 1 //2018-09-09
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <iostream>
 5 #include <algorithm>
 6 #define lson (id<<1)
 7 #define rson ((id<<1)|1)
 8 using namespace std;
 9 
10 const int N = 2000;
11 const double EPS = 0.0001;
12 
13 struct Node{
14     double sum;
15 }tree[N<<2];
16 int cnt[N], len;
17 double x[N];
18 
19 void build(){
20     memset(tree, 0, sizeof(tree));
21 }
22 
23 void update(int id, int L, int R, int pos, int val){
24     if(L==R){
25         cnt[pos] += val;
26         if(cnt[pos]>1)tree[id].sum = x[pos+1]-x[pos];
27         else tree[id].sum = 0;
28         return;
29     }
30     int mid = (L+R)/2;
31     if(pos <= mid)update(lson, L, mid, pos, val);
32     else update(rson, mid+1, R, pos, val);
33     tree[id].sum = tree[lson].sum+tree[rson].sum;
34 }
35 
36 struct Line{
37     double x0, x1, y;
38     int fg;
39     bool operator<(const Line l) const{
40         return y < l.y;
41     }
42 }line[N<<2];
43 
44 int bsearch(int l, int r, int key){
45     while(l < r){
46         int mid = (l+r)>>1;
47         if(key <= x[mid])r = mid;
48         else l = mid+1;
49     }
50     return l;
51 }
52 
53 int main()
54 {
55     int T, n, kase = 0;
56     scanf("%d",&T);
57     while(T--){
58         scanf("%d", &n);
59         double x0, y0, x1, y1;
60         len = 0;
61         for(int i = 1; i <= n; i++){
62             scanf("%lf%lf%lf%lf", &x0, &y0, &x1, &y1);
63             int a = i*2-1, b = i*2;
64             line[a].x0 = x0, line[a].x1 = x1, line[a].y = y0, line[a].fg = 1;
65             line[b].x0 = x0, line[b].x1 = x1, line[b].y = y1, line[b].fg = -1;
66             x[++len] = x0, x[++len] = x1;
67         }
68         n*=2;
69         sort(x+1, x+1+n);
70         sort(line+1, line+1+n);
71         memset(cnt, 0, sizeof(cnt));
72         build();
73         double ans = 0;
74         for(int i = 1; i <= n; i++){
75             ans += tree[1].sum*(line[i].y-line[i-1].y);
76             int l = lower_bound(x+1, x+1+n, line[i].x0)-x;
77             int r = lower_bound(x+1, x+1+n, line[i].x1)-x;
78             for(int j = l; j < r; j++){
79                 update(1, 1, n-1, j, line[i].fg);
80             }
81         }
82         printf("%.2lf
", ans+EPS);
83     }
84 
85     return 0;
86 }