Atlantis HDU - 1542 扫描线模板

一、内容

 There are several ancient Greek texts that contain descriptions of the fabled island Atlantis. Some of these texts even include maps of parts of the island. But unfortunately, these maps describe different regions of Atlantis. Your friend Bill has to know the total area for which maps exist. You (unwisely) volunteered to write a program that calculates this quantity.

Input

The input file consists of several test cases. Each test case starts with a line containing a single integer n (1<=n<=100) of available maps. The n following lines describe one map each. Each of these lines contains four numbers x1;y1;x2;y2 (0<=x1<x2<=100000;0<=y1<y2<=100000), not necessarily integers. The values (x1; y1) and (x2;y2) are the coordinates of the top-left resp. bottom-right corner of the mapped area.

The input file is terminated by a line containing a single 0. Don’t process it.

Output

For each test case, your program should output one section. The first line of each section must be “Test case #k”, where k is the number of the test case (starting with 1). The second one must be “Total explored area: a”, where a is the total explored area (i.e. the area of the union of all rectangles in this test case), printed exact to two digits to the right of the decimal point.

Output a blank line after each test case.

Sample Input

2
10 10 20 20
15 15 25 25.5
0

Sample Output

Test case #1
Total explored area: 180.00 

二、思路

• 区间更新 + 离散化
• 
• 区间更新(优化)： 由于我们增加和删除操作是成对出现的，且操作的区间相同，那么我们就不用pushdown()进行懒标记下方，因为我们用的区间是一定的，不会用到以前没有用过的区间。那么就不存在标记下方操作了。

三、代码

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 205;
struct Line {
	int st; //代表1 -1 2种状态 
	double s, e, x;
	bool operator < (const Line & w) const {
		return x < w.x; //按照x小的排在前面 
	}
} line[N];
struct Node {
	int cnt; //代表被包含的次数 
	double len; //这个区间被包含的长度 
} tr[N << 2]; 
int n, cnt, t = 1; // cnt代表离散化后数组里面元素的个数 
double fy[N], x1, x2, y1, y2; 
void build(int id, int l, int r) {
	tr[id].cnt = tr[id].len = 0;
	if (l == r) return;
	int mid = (l + r) >> 1;
	build(id << 1, l, mid);
	build(id << 1 | 1, mid + 1, r);
}
void pushup(int id, int l, int r) {
	if (tr[id].cnt){ // 代表id这个区间被覆盖了  
		tr[id].len = fy[r + 1] - fy[l]; //因为一个点代表的是一个区间 那r这个点的区间 就是[fy[r], fy[r + 1]]这段长度 
	} else if (l != r){ //如果这整个区间没有被包含 那么就由儿子区间组成 
		tr[id].len = tr[id << 1].len + tr[id << 1 | 1].len; 
	} else tr[id].len = 0; //叶子结点  
}
void update(int id, int l, int r, int x, int y, int d) {
	if (x <= l && r <= y) {
		tr[id].cnt += d;
		pushup(id, l, r); //及时更新这段区间 因为父亲区间可能需要用到我这个区间的len 
		return;
	}
	int mid = (l + r) >> 1;
	if (x <= mid) update(id << 1, l, mid, x, y, d);
	if (y > mid) update(id << 1 | 1, mid + 1, r, x, y, d);
	pushup(id, l, r); 
} 
int  find(double y) {
	return lower_bound(fy + 1, fy + 1 + cnt, y) - fy; 
}
int main() {
	while (scanf("%d", &n), n) {
		for (int i = 1, j = 1; i <= n; i++) {
			scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
			line[j].s = y1, line[j].e = y2, line[j].x = x1, line[j].st = 1, fy[j++] = y1;
			line[j].s = y1, line[j].e = y2, line[j].x = x2, line[j].st = -1, fy[j++] = y2;
		}
		sort(line + 1, line + 1 + 2 * n);
		sort(fy + 1, fy + 1 + 2 * n);
		cnt = unique(fy + 1, fy + 1 + 2 * n) - fy - 1; //获取去重后元素的个数
		build(1, 1, cnt - 1); //一个点代表的是一个区间， 一共有cnt个点 所以只有cnt-1个区间
		double ans = 0;
		for (int i = 1; i <= 2 * n; i++) {
			ans += tr[1].len * (line[i].x - line[i - 1].x);
			update(1, 1, cnt - 1, find(line[i].s), find(line[i].e) - 1, line[i].st); //这里-1是因为每个点代表的是一个区间 我们不能包含e那个点所代表的区间 
		} 
		printf("Test case #%d\nTotal explored area: %.2lf\n\n", t++, ans); 
	}
	return 0;
}