[POJ 1151] Atlantis【扫描线+离散化+线段树】

• 2018-01-08
• 0
• 0

Problem:

Description

Input

Output

Sample Input

2
10 10 20 20
15 15 25 25.5
0

Sample Output

Test case #1
Total explored area: 180.00

Source

Solution:

扫描线的定义：https://en.wikipedia.org/wiki/Sweep_line_algorithm

我的第一道扫描线。。

二维扫描线算法经典入门题，矩形覆盖问题的模板。

我们只需要抽取所有水平的边，按纵坐标从小到大排序（当然也可以从大到小）。再利用差分的思想（类比一维扫描线），每个矩形区域下边权值赋为 1，上边权值赋为 -1。

将水平边的横坐标离散化处理，以一一对应线段树的下标。

按纵坐标从小到大扫描，每次将新的边界加入线段树中，维护当前水平方向覆盖长度，每次将该长度乘上竖直方向覆盖的长度（即本次边界与下次边界的纵坐标差），统计入答案即可。

注意由于这里的长度为实数，而普通的线段树维护的是整数区间，即：

• [l, r] 在线段树上被分成 [l, m] 和 [m + 1, r]，导致 (m, m + 1) 的长度丢失。

为了避免此类间隔区域的长度丢失，我们可以将线段树改为维护 [l, r + 1] 这个区间的长度。这样的话进行 add 操作时右端点应该减 1，否则最右端会多统计 1 个下标长度！

注意每组数据后换行！

Plus: 由于数据范围较小，这道题实际上可以直接将两个维度都离散化直接统计每一块是否被覆盖。。但这样复杂度就是 O(Tn²) 了。

普通的扫描线算法资料：

• http://blog.163.com/lawyer_glass/blog/static/24343404220153182520981/
• https://www.cnblogs.com/whywhy/p/4214353.html
• https://www.cnblogs.com/scau20110726/archive/2013/04/12/3016765.html

非常高深的区域填充的扫描线算法资料：

• https://www.jianshu.com/p/d9be99077c2b
• https://wenku.baidu.com/view/530d1cd64693daef5ef73dc8.html
• http://blog.csdn.net/orbit/article/details/7368996

Code: O(Tnlogn) [180K, 16MS]

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define MAX2N 202
#define eps 1e-8
using namespace std;

inline int dsgn(const double &x){
	if(fabs(x) <= eps) return 0;
	return x < 0 ? -1 : 1;
}

int T = 0, n, topd;

struct _double{
	double val;
	
	_double() {}
	_double(double val): val(val) {}
	
	inline bool operator < (const _double &d2) const {return dsgn(val - d2.val) < 0;}
	
	inline bool operator == (const _double &d2) const {return dsgn(val - d2.val) == 0;}
};  // Overload operator == for double comparison

_double disc[MAX2N];  // Discretization of the x-axis coordinate

struct Segment{
	double _l, _r, h;
	int l, r, v;
	
	inline bool operator < (const Segment &seg2) const {return h < seg2.h;}
} seg[MAX2N];

struct Node{
	int cov;
	double sum;
};

struct Segment_Tree{
	#define MAXNODE (MAX2N << 2)
	#define lch (u << 1)
	#define rch (u << 1 | 1)
	#define smid (l + r >> 1)
	Node node[MAXNODE];
	
	inline void clear() {memset(node, 0, sizeof(node));}
	
	inline void update(int u, int l, int r){
		if(node[u].cov) node[u].sum = disc[r + 1].val - disc[l].val;  // To avoid gap missing
		else if(l == r) node[u].sum = 0;
		else node[u].sum = node[lch].sum + node[rch].sum;
	}
	
	inline void add(int u, int l, int r, int al, int ar, int v){
		if(al <= l && r <= ar){
			node[u].cov += v;
			update(u, l, r);
			return;
		}
		if(al <= smid) add(lch, l, smid, al, ar, v);
		if(smid < ar) add(rch, smid + 1, r, al, ar, v);
		update(u, l, r);
	}
} sgt;

int main(){
	while(scanf("%d", &n) != EOF && n){
		for(register int i = 1; i <= n; i++){
			double lx, ly, rx, ry;
			scanf("%lf%lf%lf%lf", &lx, &ly, &rx, &ry);
			
			Segment &uped = seg[(i << 1) - 1], &dwned = seg[i << 1];
			uped.h = lx, uped._l = ly, uped._r = ry, uped.v = 1;
			dwned.h = rx, dwned._l = ly, dwned._r = ry, dwned.v = -1;
			
			disc[(i << 1) - 1].val = ly, disc[i << 1].val = ry;
		}
		n <<= 1, sort(disc + 1, disc + n + 1);
		topd = unique(disc + 1, disc + n + 1) - disc - 1;
		for(register int i = 1; i <= n; i += 2){
			seg[i].l = seg[i + 1].l = lower_bound(disc + 1, disc + topd + 1, _double(seg[i]._l)) - disc;
			seg[i].r = seg[i + 1].r = lower_bound(disc + 1, disc + topd + 1, _double(seg[i]._r)) - disc;
		}
		// Discretize the x-axis coordinate
		sort(seg + 1, seg + n + 1);
		double area = 0; sgt.clear();
		for(register int i = 1; i < n; i++){
			sgt.add(1, 1, topd, seg[i].l, seg[i].r - 1, seg[i].v);  // Upper bound decrease 1 for the right-extra interval !!!
			area += (seg[i + 1].h - seg[i].h) * sgt.node[1].sum; 
		}
		printf("Test case #%d\n", ++T);
		printf("Total explored area: %.2f\n\n", area);  // Beware of the presentation !!!
	}
	return 0;
}