HDU 1542

题目链接：

　　http://acm.hdu.edu.cn/showproblem.php?pid=1542

题目大意：

　　给定N个矩形，求所有矩形覆盖的总面积。

解题思路：

　　线段树扫描线求解矩形面积并的问题。关于线段树扫描线的思想可以看一下这篇博客：http://www.51itong.net/hdu-1542-atlantis-10251.html

　　主要理解要点就是线段树的叶节点是一个区间而非一个点，例如有m个点那么就有m-1个区间，而线段树的叶子节点也就有m-1个。

　　还有就是pushUp(l, r, rt)的操作，当该区间cnt[rt]>0时，说明这一段区间的长度应该被计算在内，则更新该节点的长度。当l==r时，说明不存在区间要进行计算，sum[rt]=0。其他的情况就是cnt[rt]==0且l != r的情况了，这时候说明有一条线段要被切掉，由下向上更新sum的值。

代码：

 1 #include <iostream>
 2 #include <cmath>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <map>
 6 #include <vector>
 7 #include <algorithm>
 8 using namespace std;
 9 
10 #define ll long long
11 #define INF 0x3f3f3f3f
12 #define LL_INF 0x3f3f3f3f3f3f3f3f
13 #define MAX 2222
14 
15 struct Seg
16 {
17     double l, r, h;
18     int d;
19     Seg() {}
20     Seg(double a, double b, double c, int e) : l(a), r(b), h(c), d(e) {}
21     bool operator < (const Seg &ss) const{
22         return h < ss.h;
23     }
24 };
25 
26 Seg seg[MAX << 2];
27 int cnt[MAX << 2];
28 double X[MAX << 2], sum[MAX << 2];
29 
30 void pushUp(int l, int r, int rt) 
31 {
32     if (cnt[rt]) sum[rt] = X[r+1] - X[l];
33     else if (l == r) sum[rt] = 0;
34     else sum[rt] = sum[rt << 1] + sum[rt << 1|1];
35 }
36 
37 void update(int L, int R, int c, int l, int r, int rt)
38 {
39     if (L <= l && R >= r) {
40         cnt[rt] += c;
41         pushUp(l, r, rt);
42         return;
43     }
44     int m = (l + r) >> 1;
45     if(L <= m) update(L, R, c, l, m, rt << 1);
46     if(R > m) update(L, R, c, m + 1, r, rt << 1|1);
47     pushUp(l, r, rt);
48 }
49 
50 int Bin(double key, int n, double X[])
51 {
52     int l = 0, r = n - 1;
53     while (l <= r) {
54         int m = (l + r) >> 1;
55         if (X[m] == key) return m;
56         if (X[m] > key) r = m - 1;
57         else if (X[m] < key) l = m + 1;
58     }
59     return -1;
60 }
61 
62 int main()
63 {
64     //freopen("debug\in.txt", "r", stdin);
65     //freopen("CON", "w", stdout);
66     int i, j, k;
67     int n, kase = 1;
68     while (~scanf("%d", &n) && n) {
69         double a, b, c, d;
70         int m = 0;
71         for (i = 0; i < n; ++i) {
72             scanf("%lf%lf%lf%lf", &a, &b, &c, &d);
73             seg[m] = Seg(a, c, b, 1);
74             X[m++] = a;
75             seg[m] = Seg(a, c, d, -1);
76             X[m++] = c;
77         }
78         sort(X, X + m);
79         sort(seg, seg + m);
80         k = 1;
81         for (i = 1; i < m; ++i) {
82             if (X[i] != X[i-1]) X[k++] = X[i];
83         }
84 
85         memset(sum, 0, sizeof(sum));
86         memset(cnt, 0, sizeof(cnt));
87         double res = 0;
88         for (i = 0; i < m - 1; ++i) {
89             int l = Bin(seg[i].l, k, X);
90             int r = Bin(seg[i].r, k, X) - 1;
91             if (l <= r) update(l, r, seg[i].d, 0, k - 1, 1);
92             res += sum[1] * (seg[i+1].h - seg[i].h);
93         }
94         printf("Test case #%d
", kase++);
95         printf("Total explored area: %.2lf

", res);
96     }
97     return 0;
98 }