覆盖的面积 HDU

给定平面上若干矩形,求出被这些矩形覆盖过至少两次的区域的面积.

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

和求面积并差不多。

 1 #pragma warning(disable:4996)
 2 #include<cstdio>
 3 #include<stack>
 4 #include<cmath>
 5 #include<string>
 6 #include<cstring>
 7 #include<iostream>
 8 #include<algorithm>
 9 using namespace std;
10 
11 #define lson root<<1
12 #define rson root<<1|1
13 #define ll long long
14 
15 const int maxn = 5000;
16 
17 struct Seg {
18     int d;
19     double l, r, h;
20     Seg(){}
21     Seg(double l, double r, double h, int d) : l(l), r(r), h(h), d(d) {}
22     bool operator<(const Seg& rhs) { return h < rhs.h; }
23 }line[maxn];
24 
25 int n, cnt[maxn];
26 double Hash[maxn], one[maxn], two[maxn];
27 
28 void Push_up(int l, int r, int root) {
29     if (cnt[root] >= 2) two[root] = one[root] = Hash[r] - Hash[l];
30     else if (cnt[root] == 1) {
31         one[root] = Hash[r] - Hash[l];
32         if (l + 1 == r) two[root] = 0;
33         else two[root] = one[lson] + one[rson];
34     }
35     else {
36         if (l + 1 == r) one[root] = two[root] = 0;
37         else {
38             one[root] = one[lson] + one[rson];
39             two[root] = two[lson] + two[rson];
40         }
41     }
42 }
43 
44 void Update(int L, int R, int l, int r, int root, int c) {
45     if (l >= R || r <= L) return;
46     if (L <= l && r <= R) {
47         cnt[root] += c;
48         Push_up(l, r, root);
49         return;
50     }
51     int mid = (l + r) >> 1;
52     Update(L, R, l, mid, lson, c);
53     Update(L, R, mid, r, rson, c);
54     Push_up(l, r, root);
55 }
56 
57 int main()
58 {
59     int kase;
60     scanf("%d", &kase);
61     while (kase--) {
62         scanf("%d", &n);
63         double x1, y1, x2, y2;
64         for (int i = 1; i <= n; i++) {
65             scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
66             line[i] = Seg(x1, x2, y1, 1);
67             Hash[i] = x1;
68             line[i + n] = Seg(x1, x2, y2, -1);
69             Hash[i + n] = x2;
70         }
71         
72         n <<= 1;
73         sort(line + 1, line + n + 1);
74         sort(Hash + 1, Hash + n + 1);
75 
76         int m = unique(Hash + 1, Hash + n + 1) - (Hash + 1);
77 
78         memset(cnt, 0, sizeof(cnt));
79         memset(one, 0, sizeof(one));
80         memset(two, 0, sizeof(two));
81 
82         double ans = 0;
83         for (int i = 1; i <= n; i++) {
84             int l = lower_bound(Hash + 1, Hash + m + 1, line[i].l) - Hash;
85             int r = lower_bound(Hash + 1, Hash + m + 1, line[i].r) - Hash;
86             Update(l, r, 1, m, 1, line[i].d);
87             ans += two[1] * (line[i + 1].h - line[i].h);
88         }
89         printf("%.2lf
", ans);
90     }
91 }