首页 > 代码库 > POJ 1151 Atlantis（线段树 + 扫描线）
POJ 1151 Atlantis（线段树 + 扫描线）
转载请注明原文：http://www.cnblogs.com/burning-flame/p/5934653.html
题目链接：http://poj.org/problem?id=1151
题意：
给你 n 个矩形的对角线坐标，求 n 个矩形并集的面积。
做法：
扫描线 + 线段树。
因为作线段树的题遇到了扫描线，只是粗浅的了解了一下。
就像字面上的：线性扫描一遍，对于每个单元，因为某些事件的发生会有一些变化。
举个例子：
现有长度为 n 的数组a，同时有 n 个区间覆盖[li, ri]，对于每个区间，它会把对应区间的数组元素 +1，问最后数组中元素值?
可以把每个覆盖看为一个事件，一个li代表一个覆盖事件的开始，同样一个ri代表一个覆盖事件的结束。这样，对于这个例子，就是线性对数组元素扫描一遍。元素ai被覆盖次数 = ai-1被覆盖的次数 + 覆盖事件从 i 开始的数目 - 覆盖事件从 i-1 结束的数目（不会影响到元素 i）。
所以代码如下：
#include <iostream>#include <cstdio>#include <cstring>#include <map>#include <queue>#include <set>#include <cmath>#include <cstdlib>#include <algorithm>#define lson (i<<1)#define rson (lson|1)using namespace std;typedef long long LL;const int N = 207;const int INF = 0x7fffffff;map<int, int> mpL;map<int, int> mpR;int main(){ int num[N]; int n; while (scanf("%d", &n) != EOF) { mpL.clear(); mpR.clear(); memset(num, 0, sizeof(num)); for (int i = 0; i < n; i++) { int a, b; scanf("%d%d", &a, &b); mpL[a]++; mpR[b]++; } num[1] = mpL[1]; for (int i = 2; i <= n; i++) num[i] = num[i-1] + mpL[i] - mpR[i-1]; for (int i = 1; i <= n; i++) printf("%d%c", num[i], i == n ? ‘\n‘ : ‘ ‘); } return 0;}
而对于这道题：
推荐博客（图画的很清晰）：Coder and Writer的博客
思路：
对于x，y轴，选一个方向建线段树（假设以 x 轴建树，那么以矩形的竖线 x 值离散化处理建树，把矩形的横线看作一个个覆盖事件，以 y 值从小到大排序。）
选另一个方向扫描，对于每一个单元，会有若干事件的发生（使用flag，对于一个矩形的两个横线，靠近 x 轴的横线的flag赋值为 1 代表覆盖，另一个的flag赋值为-1则代表删除之前覆盖的线），在一个单元内发生若干事件同时更新线段树 x 轴被覆盖的长度（sum[1]即是），再乘以当前单元对应的长度即为扫面单元对应并集的面积，扫描过程中累加即可。
代码实现：
离散化。 dis数组统计 x 轴上轴任意两条竖线间距。
cover数组的使用很巧妙。代表当前区间[l, r]被覆盖次数。若当前区间有被 事件 覆盖，之间初始化为对应 x 轴的间距即可，然后向上push_up到根。而当当前区间的所有覆盖被删除时，其子区间可能仍然有覆盖，当当前区间有覆盖时，因为直接初始化并且push_up所以跟子区间的覆盖没有关系。这样就达到了求被覆盖的并集的效果。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <map>#include <queue>#include <set>#include <cmath>#include <cstdlib>#include <algorithm>#define lson (i<<1)#define rson (lson|1)using namespace std;typedef long long LL;const int N = 207;const int INF = 0x7fffffff;struct line{ double y, x1, x2; int flag;}ln[N<<2];int n, cnt, cnt_ln, cover[N<<2];double sum[N<<2], dis[N];map<double, int> mp, mpy;int cmp(struct line a, struct line b){ return a.y < b.y;}void push_up(int L, int R, int i){ if (cover[i]) sum[i] = dis[R] - dis[L-1]; else if (L == R) sum[i] = 0; else sum[i] = sum[lson] + sum[rson];}void update(int L, int R, int l, int r, int val, int i){ if (L == l && R == r) { cover[i] += val; push_up(L, R, i); return; } int mid = (L + R) >> 1; if (r <= mid) update(L, mid, l, r, val, lson); else if (l > mid) update(mid + 1, R, l, r, val, rson); else { update(L, mid, l, mid, val, lson); update(mid + 1, R, mid + 1, r, val, rson); } push_up(L, R, i);}int main(){ //freopen("in.ads", "r", stdin); int cas = 0; while (scanf("%d", &n) != EOF && n) { double ans = 0; cnt = 0; dis[0] = 0; cnt_ln = 0; mp.clear(); mpy.clear(); memset(cover, 0, sizeof(cover)); memset(sum, 0, sizeof(sum)); for (int i = 0; i < n; i++) { double x1, x2, y1, y2; scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2); ln[cnt_ln].y = y1; ln[cnt_ln].x1 = x1; ln[cnt_ln].x2 = x2; ln[cnt_ln].flag = 1; cnt_ln++; ln[cnt_ln].y = y2; ln[cnt_ln].x1 = x1; ln[cnt_ln].x2 = x2; ln[cnt_ln].flag = -1; cnt_ln++; mp[x1] = 1; mp[x2] = 1; mpy[y1]++; mpy[y2]++; } for (map<double, int>::iterator it = mp.begin(); it != mp.end(); it++) { it->second = ++cnt; map<double, int>::iterator it1 = ++it; it--; if (it1 != mp.end()) dis[cnt] = dis[cnt-1] + it1->first - it->first; } sort(ln, ln + cnt_ln, cmp); int idx = 0; for (map<double, int>::iterator it = mpy.begin(); it != mpy.end(); it++) { int cnt1 = 0; for (; idx < cnt_ln && cnt1 < it->second; idx++) { update(1, cnt - 1, mp[ln[idx].x1], mp[ln[idx].x2] - 1, ln[idx].flag, 1); cnt1++; } if (it != --mpy.end()) { map<double, int>::iterator it1 = ++it; it--; ans += sum[1] * (it1->first - it->first); } } printf("Test case #%d\nTotal explored area: %.2lf\n\n", ++cas, ans); } return 0;}
POJ 1151 Atlantis（线段树 + 扫描线）