HDU_1542_扫描线求面积(线段树维护)

HDU 1542

  • 一条竖直直线从左到右(反向也行)扫描,那么将扫描出来的直线的y坐标离散化,然后用线段树维护y轴的覆盖区间.x值作为高度
  • 如果一条横着直线从下到上(反向也行)扫描,将扫描出来的x坐标离散化,线段树维护x轴的覆盖区间,y作为高度.
  • 此题从上到下扫,将x坐标离散化,建树
  • 将一个矩形的2条边标记为上边1和下边-1,用线段树维护时不需要延迟标记,因为成对出现,下一次对应边出现就会消去此次覆盖.
  • 但是线段树端点出问题,一条上边[1,3],一条下边[3,5],3最后覆盖值为0,就会少算一个覆盖点,方法:线段树的右端都-1变成[1,2] [3,4],
  • 线段树节点维护2个信息,sum[]:覆盖长度,add[]:节点被覆盖的次数,
  1. add>0,该节点的sum = x[right+1] - x[left]
  2. add = 0,该节点没有被覆盖,那么覆盖区间是子节点的覆盖区间:sum=sum[2*p]+sum[2*p+1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
#include <string.h>
#include <algorithm>
#define lson p<<1,left,mid
#define rson p<<1|1,mid+1,right
using namespace std;
const int maxn = 2000+5;

int add[maxn << 2];
double x[maxn<<2],sum[maxn<<2];
int n, cnt, res;

struct node {
	double l, r, h;
	int s;
	node() {};
	node(double ll,double rr,double hh,int ss) {
		l = ll; r = rr; h = hh; s = ss;
	}
	bool operator<(const node& temp)const {
		return h < temp.h;
	}
}s[maxn];
void pushup(int p,int left,int right) {
	if (add[p]) sum[p] = x[right + 1] - x[left]; //得到长度
	else if (left == right) sum[p] = 0; //[x[right+1],x[left]],由于没有覆盖所以=0
	else sum[p] = sum[p << 1] + sum[p<<1|1];//向上更新长度
}
void updata(int L,int R,int val,int p,int left,int right) {
	if (L <= left && right <= R) {
		add[p] += val;
		pushup(p,left,right);
		return;
	}
	int mid = (left + right) >>1;
	if (L <= mid) updata(L,R,val,lson);
	if (mid < R) updata(L,R,val,rson);
	pushup(p,left,right);
}
//int binary_find(double val) {
//	int left = -1, right = res - 1;
//	while (right - left > 1) {
//		int mid = (left + right)>>1;
//		if (x[mid] >= val) right = mid;
//		else left = mid;
//	}
//	return right;
//}
int binary_find(double val) {
	int left = 0, right = res - 1;
	while (left <= right) {
		int mid = (left + right) >> 1;
		if (x[mid] < val) left = mid + 1;
		else right = mid - 1;
	}
	return left;
}
int main() {
	int count = 1; //freopen("a.txt","r",stdin);
	while (scanf("%d",&n) != EOF && n) {
		cnt = 0;
		for (int i = 0; i < n; i++) {
			double a, b, c, d;
			scanf("%lf%lf%lf%lf",&a,&b,&c,&d); //a,b是左上角的点， c,d,是右上角的点
			s[cnt] = node(a,c,b,1);
			x[cnt++] = a; //横坐标存下来,进行离散化
			s[cnt] = node(a,c,d,-1);
			x[cnt++] = c;
		}
		sort(s,s+cnt); //扫描线按高度排序
		sort(x,x+cnt); //离散化的坐标进行排序
		res=1; //去重的辅助标记
		for (int i = 1; i < cnt; i++)
			if (x[i] != x[i - 1]) x[res++] = x[i];//将相同的去重,移到前面去
		memset(add,0,sizeof add);
		memset(sum,0,sizeof sum);
		double ans = 0;
		for (int i = 0; i < cnt-1; i++) {
			int l = binary_find(s[i].l);
			int r = binary_find(s[i].r) - 1; //在x中找到离散后的坐标
			updata(l,r,s[i].s,1,0,res-1); //res是去重后坐标的总数+1
			ans += sum[1] * (s[i+1].h - s[i].h);
		}
		printf("Test case #%d\nTotal explored area: %.2lf\n\n", count++, ans);
	}
	return 0;
}