poj - 1177 - Picture（离线化+扫描线+线段树）

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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <cstdio>
#include <algorithm>
using namespace std;
#define lc (o<<1)
#define rc ((o<<1) + 1)
const int MAXN = 5000;
int y[MAXN<<1], cnt;
struct ScanLine {
int x;
int y1, y2;
bool is_left;
bool operator < (const ScanLine& e) const {
return x < e.x;
}
} scanlines[MAXN<<1];
struct Node {
int L, R;
int len;
int segs;
int cover;
int lcover, rcover;
} nodes[MAXN << 3];
void build(int o, int L, int R) {
nodes[o].L = L;
nodes[o].R = R;
nodes[o].len = 0;
nodes[o].segs = 0;
nodes[o].cover = 0;
nodes[o].lcover = 0;
nodes[o].rcover = 0;
if(L + 1 == R) return;
int M = (L + R) >> 1;
build(lc, L, M);
build(rc, M, R);
}
int point_to(int x) {
//离散化后找映射值
return lower_bound(y, y + cnt, x) - y;
}
void maintain_len(int o) {
//维护区间覆盖长度
if(nodes[o].cover > 0) {
nodes[o].len = y[nodes[o].R] - y[nodes[o].L];
}
else if(nodes[o].L + 1 == nodes[o].R) {
nodes[o].len = 0;
}
else {
nodes[o].len = nodes[lc].len + nodes[rc].len;
}
}
void maintain_segs(int o) {
//维护区间连续线段数
if(nodes[o].cover > 0) {
nodes[o].segs = 1;
nodes[o].lcover = nodes[o].rcover = 1;
}
else if(nodes[o].L + 1 == nodes[o].R) {
nodes[o].segs = 0;
nodes[o].lcover = 0;
nodes[o].rcover = 0;
}
else {
nodes[o].segs = nodes[lc].segs + nodes[rc].segs - nodes[lc].rcover*nodes[rc].lcover;
nodes[o].lcover = nodes[lc].lcover;
nodes[o].rcover = nodes[rc].rcover;
}
}
void my_insert(int o, int ql, int qr) {
//线段树插入
if(ql <= nodes[o].L && nodes[o].R <= qr) {
nodes[o].cover++;
maintain_len(o);
maintain_segs(o);
return;
}
int M = (nodes[o].L + nodes[o].R) >> 1;
if(ql < M) my_insert(lc, ql, qr);
if(qr > M) my_insert(rc, ql, qr);
maintain_len(o);
maintain_segs(o);
}
void my_delete(int o, int ql, int qr) {
//线段树删除
if(ql <= nodes[o].L && nodes[o].R <= qr) {
nodes[o].cover--;
maintain_len(o);
maintain_segs(o);
return;
}
int M = (nodes[o].L + nodes[o].R) >> 1;
if(ql < M) my_delete(lc, ql, qr);
if(qr > M) my_delete(rc, ql, qr);
maintain_len(o);
maintain_segs(o);
}
int main()
{
int n, x1, y1, x2, y2;
while(scanf("%d", &n) == 1) {
for(int i = 0; i < n; i++) {
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
scanlines[i<<1].x = x1;
scanlines[i<<1].y1 = y1;
scanlines[i<<1].y2 = y2;
scanlines[i<<1].is_left = true;
scanlines[(i<<1)+1].x = x2;
scanlines[(i<<1)+1].y1 = y1;
scanlines[(i<<1)+1].y2 = y2;
scanlines[(i<<1)+1].is_left = false;
y[i<<1] = y1;
y[(i<<1)+1] = y2;
}
sort(y, y + 2*n);
//离散化
cnt = unique(y, y + 2*n) - y;
build(1, 0, 2*n-1);
sort(scanlines, scanlines + 2*n);
int perimeter = 0;
//周长
int last_len = 0;
//上一次整棵线段树已覆盖的长度
for(int i = 0; i < 2*n-1; i++) {
//2n条扫描线依次进行扫描
if(scanlines[i].is_left) {
//入边插入
my_insert(1, point_to(scanlines[i].y1), point_to(scanlines[i].y2));
}
else {
//出边删除
my_delete(1, point_to(scanlines[i].y1), point_to(scanlines[i].y2));
}
perimeter += (scanlines[i+1].x - scanlines[i].x) * 2 * nodes[1].segs;
//加横边
perimeter += abs(nodes[1].len - last_len);
//加竖边
last_len = nodes[1].len;
}
my_delete(1, point_to(scanlines[2*n-1].y1), point_to(scanlines[2*n-1].y2));
perimeter += abs(nodes[1].len - last_len);
printf("%dn", perimeter);
}
return 0;
}