【线段树 扫描线】HDU 1255 覆盖的面积
2021-09-28 10:59:00 # ACM

题链

题目解析

扫描线模板题，求被覆盖两次及以上的区域面积；

线段树维护区间覆盖次数，被覆盖一次的总长度 $len1$ ，被覆盖两次的总长度 $len2$；

对区间覆盖次数 $cnt$ 分类讨论：
  $1.$ $cnt >= 2$，那么 $len1,len2$ 覆盖完全；
  $2.$ $cnt == 1$，那么 $len1$ 覆盖完全，$len2$ 为左右孩子的 $len1$ 之和；
  $3.$ $cnt == 0$，那么 $lem1,len2$ 分别为为左右孩子的 $len1,len2$ 之和；

代码实现

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
//#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
#include <unordered_map>
#include <deque>
#include <stack>
using namespace std;
#define ls rt<<1
#define rs rt<<1|1
#define LL long long
#define ll long long
#define MAXN 200000
#define mod 1000000007
#define MS 1009

int n,m;
struct node{
	double l,r,h;
	int w;
}li[MS<<1]; int tot;
double dx[MS<<1]; int totx;
struct nod{
	double len1;
	double len2;
	int cnt;
}p[MS<<3];

bool cmp(node t1, node t2){
	if (t1.h == t2.h) return t1.w > t2.w;
	return t1.h < t2.h;
}

void build(int l,int r,int rt){
	p[rt] = {0,0,0};
	if (l == r) return;
	int m = l+r>>1;
	build(l,m,ls); build(m+1,r,rs);
}

void push_up(int rt,int l,int r){
	if (p[rt].cnt > 1) p[rt].len1 = p[rt].len2 = dx[r+1] - dx[l];
	else if (p[rt].cnt == 1){
		p[rt].len1 = dx[r+1] - dx[l];
		if (l == r) p[rt].len2 = 0;
		else p[rt].len2 = p[ls].len1 + p[rs].len1;
	} 
	else{
		if (l == r) p[rt].len1 = p[rt].len2 = 0;
		else {
			p[rt].len1 = p[ls].len1 + p[rs].len1;
			p[rt].len2 = p[ls].len2 + p[rs].len2;
		}
	}
}

void modify(int L,int R,int l,int r,int rt,int w){
	if (L <= l && r <= R){
		p[rt].cnt += w;
		push_up(rt,l,r);
		return;
	}
	int m = l+r>>1;
	if (m >= L) modify(L,R,l,m,ls,w);
	if (m <  R) modify(L,R,m+1,r,rs,w);
	push_up(rt,l,r);
}

void solve(){
	scanf("%d",&n); tot = 0; 
	for (int i=1;i<=n;i++){
		double x1,y1,x2,y2; scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
		li[++tot] = {x1,x2,y1, 1}; dx[tot] = x1;
		li[++tot] = {x1,x2,y2,-1}; dx[tot] = x2;
	}
	sort(dx+1,dx+tot+1); totx = 1; for (int i=2;i<=tot;i++) if (dx[i] != dx[i-1]) dx[++totx] = dx[i];
	sort(li+1,li+tot+1,cmp);
	build(1,totx-1,1);
	double ans = 0;
	//for (int i=1;i<=tot;i++){
	//	cout << li[i].l << " " << li[i].r << " " << li[i].h << " " << li[i].w << "\n";
	//}
	for (int i=1;i<tot;i++){
		double now = p[1].len2;
		int L = lower_bound(dx+1,dx+totx+1,li[i].l) - dx;
		int R = lower_bound(dx+1,dx+totx+1,li[i].r) - dx;
		modify(L,R-1,1,totx-1,1,li[i].w);
		ans += p[1].len2*(li[i+1].h-li[i].h);
		//cout << i << ": " << p[1].len2 << "\n";
	}
	printf("%.2f\n",ans);
}

int main(){
	//ios::sync_with_stdio(false);
	int ce = 1;
	cin >> ce;
	while (ce--){
		solve();
	}
		
	return 0;	
}
Prev
2021-09-28 10:59:00 # ACM
Next