HDU 1542 Atlantis（扫描线经典入门题

Problem Description

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

题意

求矩形覆盖的面积总和

分析

首先介绍扫描线的思想

先给个图
下面开始介绍扫描线！

看这个图，我们将矩形每一个宽作为一个边界。
总面积可以看作是三个部分的矩形面积加起来！
我们定义当前的有效长度为当前矩形的宽
红色的线就是我们说的扫描线，用这条线从左往右扫，每次扫到一个边界，就更新当前的有效长度。
那么 $每一部分的面积 = 有效长度 * 边界的距离$
这就是扫描线的思想。

接下来介绍具体实现

首先为了从左往右扫描，当然要将每一条宽按 $x$ 从小到大排序。
每一条宽储存的是 $y_{1}$ 和 $y_{2}$ 。
用扫描线扫描之后，我们将问题转化成这样一个小问题：
有若干条线段，怎么维护并起来的总长度。
问题来了，题目中给的坐标是 $d o u b l e$ 类型的。无法直接用线段树啊！
所以要离散化！
我们将每个 $y$ 从大到小进行排名。
如图

这样子我们对于每一条线段，都能得知他覆盖的区间。
比如黑色线段覆盖了 $[1, 4]$ ，蓝色覆盖了 $[2, 6]$ ，红色覆盖了 $[3, 5]$
但是点是离散的，线段是连续的，所以我们用覆盖了那些线段来表示。
这里首先定义 $i$ 到 $i + 1$ 这条线段的编号是 $i$ （用点的编号来指代连着的边
假设有 $m$ 个点，那么有 $m - 1$ 条边，编号为 $1$ 到 $m - 1$
所以黑色线段覆盖了 $[1, 3]$ 的线段，蓝色覆盖了 $[2, 5]$ 的线段，红色覆盖了 $[3, 5]$ 的线段
于是我们可以用线段树来进行维护了。

线段树里该存什么？

首先要存的肯定是有效长度了。
还要存的是一个标记，指的是当前节点代表的区间被覆盖了多少层（注意这是区间的性质，不由子区间来，也不由父区间来，即这个标记既不 $p u s h u p$ 也不 $p u s h d o w n$ ）。
所以要存的是一个标记还有有效长度。
然后就可以进行更新了。
更新部分代码如下：

void update(int l, int r, int rt, int a, int b, int c){
	if(l >= a && r <= b){
		tag[rt] += c;
		pushup(rt, l, r);
		return;
	}
	int m = l + r >> 1;
	if(a <= m) update(lson, a, b, c);
	if(b > m) update(rson, a, b,c);
	pushup(rt, l, r);
}

~~可以说是很朴素了~~
确实很朴素啊！
$p u s h u p$ 代码如下：

void pushup(int rt, int l, int r){
	if(add[rt]) sum[rt] = e[r + 1] - e[l];
	else sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}

也是很简单的啦
非常非常好理解

总代码如下

#include <bits/stdc++.h>
#define N 100005
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
using namespace std;
struct node{
	double l, r, x;
	int f;
	bool operator < (const node & A) const{
		return x < A.x;
	}
}line[N * 2];
int add[N * 4], ret, tot, cnt;
double sum[N * 4], a, b, c, d, ans, e[N * 2];
set<double> s;
void cr(double a, double b, double c, int d){
	line[++tot].x = a; line[tot].l = b; line[tot].r = c; line[tot].f = d;
}
void pushup(int rt, int l, int r){
	if(add[rt]) sum[rt] = e[r + 1] - e[l];
	else sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
void update(int l, int r, int rt, int a, int b, int c){
	if(l >= a && r <= b){
		add[rt] += c;
		pushup(rt, l, r);
		return;
	}
	int m = l + r >> 1;
	if(a <= m) update(lson, a, b, c);
	if(b > m) update(rson, a, b, c);
	pushup(rt, l, r);
}
int main(){
	int i, j, n, m, l, r;
	while(scanf("%d", &n)){
		if(!n) break;
		ret++;
		tot = ans = cnt = 0;
		memset(sum, 0, sizeof(sum));
		memset(add, 0, sizeof(add));
		for(i = 1; i <= n; i++){
			scanf("%lf%lf%lf%lf", &a, &b, &c, &d);
			cr(a, b, d, 1);
			cr(c, b, d, -1);
			e[++cnt] = b; e[++cnt] = d;
		}
		sort(line + 1, line + tot + 1);
		sort(e + 1, e + cnt + 1);
		m = unique(e + 1, e + cnt + 1) - e - 1;
		for(i = 1; i < tot; i++){
			l = lower_bound(e + 1, e + cnt + 1, line[i].l) - e;
			r = lower_bound(e + 1, e + cnt + 1, line[i].r) - e;
			update(1, m, 1, l, r - 1, line[i].f);	
			ans += sum[1] * (line[i + 1].x - line[i].x);
		}
		printf("Test case #%d\n", ret);
		printf("Total explored area: %.2lf\n", ans);
		printf("\n");
	}
	return 0;
}