HDOJ 1542 线段树矩形面积并

链接：

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

题意：

给你n个矩形，问你这个矩形覆盖的面积

题解：

就是线段树+扫描线+坐标离散化，详情在代码里面

代码：

 1 #include <map>
 2 #include <set>
 3 #include <cmath>
 4 #include <queue>
 5 #include <stack>
 6 #include <cstdio>
 7 #include <string>
 8 #include <vector>
 9 #include <cstdlib>
10 #include <cstring>
11 #include <sstream>
12 #include <iostream>
13 #include <algorithm>
14 #include <functional>
15 using namespace std;
16 #define rep(i,a,n) for (int i=a;i<n;i++)
17 #define per(i,a,n) for (int i=n-1;i>=a;i--)
18 #define all(x) (x).begin(),(x).end()
19 #define pb push_back
20 #define mp make_pair
21 #define lson l,m,rt<<1  
22 #define rson m+1,r,rt<<1|1 
23 typedef long long ll;
24 typedef vector<int> VI;
25 typedef pair<int, int> PII;
26 const ll MOD = 1e9 + 7;
27 const int INF = 0x3f3f3f3f;
28 const int MAXN = 210;
29 // head
30 
31 int cover[MAXN << 2];   //记录某个区间被覆盖次数
32 double x[MAXN << 1];    //对x进行离散化
33 double sum[MAXN << 2];  //记录某个区间的下底边总长度 
34 
35 struct seg {
36     double l, r, h;
37     int d;
38     const bool operator<(const seg &t) const {
39         return h < t.h;
40     }
41 }s[MAXN << 1];
42 
43 void pushup(int l, int r, int rt) {
44     if (cover[rt]) sum[rt] = x[r + 1] - x[l];　　//表示该区间至少被覆盖一次
45     else if (l == r) sum[rt] = 0;         　　   //叶子结点则底边长度为0(区间内线段长度为0)   
46     else sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
47 }
48 
49 void update(int L, int R, int d, int l, int r, int rt) {
50     if (L <= l && r <= R) {  //更新该区间下底边总长以及覆盖次数
51         cover[rt] += d;      //更新覆盖次数，因为先加后减，所以不会是负数 
52         pushup(l, r, rt);    //更新底边长   
53         return;
54     }
55     int m = (l + r) >> 1;
56     if (L <= m) update(L, R, d, lson);
57     if (R > m) update(L, R, d, rson);
58     pushup(l, r, rt);
59 }
60 
61 int main() {
62     int n, cas = 1;
63     while (cin >> n, n) {
64         int k = 0;
65         rep(i, 0, n) {
66             double x1, y1, x2, y2;
67             scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
68             x[k] = x1;
69             s[k++] = seg{ x1, x2, y1, 1 };
70             x[k] = x2;
71             s[k++] = seg{ x1, x2, y2, -1 };
72         }
73         sort(x, x + k);
74         sort(s, s + k);
75         int m = 1;
76         rep(i, 1, k) if (x[i] != x[i - 1]) x[m++] = x[i];    //去重
77         double ans = 0;
78         rep(i, 0, k) {
79             int L = lower_bound(x, x + m, s[i].l) - x;
80             int R = lower_bound(x, x + m, s[i].r) - x - 1;
81             update(L, R, s[i].d, 0, m - 1, 1);        //更新底边长度和覆盖次数，注意区间为[0,m-1]
82             ans += sum[1] * (s[i + 1].h - s[i].h);    //sum[1]存的就是总长度
83         }
84         printf("Test case #%d
Total explored area: %.2f

", cas++, ans);
85     }
86     return 0;
87 }

HDOJ 1542 线段树 矩形面积并

链接：

题意：

题解：

代码：

HDOJ 1542 线段树矩形面积并