扫描线
- 矩形面积并
将矩形划分为每个 行块 ， 一一统计出边和入边， 计算每条边的贡献， 以每条边计算 S1
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
using namespace std;
using i64 = long long;
struct Scanline {
int n, num;
vector<int> tag;
vector<i64> len, xx;
i64 S;
struct Line {
i64 y, lx, rx;
int flag; // 1是入边，-1是出边
Line() {}
Line(i64 y, i64 lx, i64 rx, int flag)
: y(y), lx(lx), rx(rx), flag(flag) {}
bool operator<(const Line& other) const { return this->y < other.y; }
};
vector<Line> line;
Scanline(int n) : n(n), num(0), S(0) {
tag.assign(n * 16 + 1, 0);
len.assign(n * 16 + 1, 0);
}
void add(i64 x1, i64 x2, i64 y1, i64 y2) {
line.emplace_back(y1, x1, x2, 1);
xx.push_back(x1);
line.emplace_back(y2, x1, x2, -1);
xx.push_back(x2);
}
void pushup(int s, int t, int p) {
if (tag[p]) {
len[p] = xx[t] - xx[s];
} else if (s + 1 == t) {
len[p] = 0;
} else {
len[p] = len[p * 2] + len[p * 2 + 1];
}
}
void update(int l, int r, int flag, int s, int t, int p) {
if (l <= s && t <= r) {
tag[p] += flag;
pushup(s, t, p);
return;
}
int m = (s + t) / 2;
if (l < m) update(l, r, flag, s, m, p * 2);
if (r > m) update(l, r, flag, m, t, p * 2 + 1);
pushup(s, t, p);
}
void init() {
sort(xx.begin(), xx.end());
sort(line.begin(), line.end());
num = unique(xx.begin(), xx.end()) - xx.begin();
}
void work() {
init();
for (int i = 0; i < line.size(); i++) {
if (i > 0) {
S += len[1] * (line[i].y - line[i - 1].y);
}
int l = lower_bound(xx.begin(), xx.begin() + num, line[i].lx) - xx.begin();
int r = lower_bound(xx.begin(), xx.begin() + num, line[i].rx) - xx.begin();
update(l, r, line[i].flag, 0, num - 1, 1);
}
}
i64 get_area() {
return S;
}
};
注意： 该线段树使用的是左闭右开区间。
- 矩形周长并：
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
struct Scanline { //周长并
int n, num;
vector<int> tag;
vector<i64> len, xx;
i64 C;
struct Line {
i64 y, lx, rx;
int flag; // 1是入边，-1是出边
Line() {}
Line(i64 y, i64 lx, i64 rx, int flag)
: y(y), lx(lx), rx(rx), flag(flag) {}
bool operator<(const Line& other) const {
if (this->y != other.y) return this->y < other.y;
else return this->flag > other.flag;
}
};
vector<Line> line;
Scanline(int n) : n(n), num(0), C(0) {
tag.assign(n * 16 + 1, 0);
len.assign(n * 16 + 1, 0);
}
void add(i64 x1, i64 x2, i64 y1, i64 y2) {
line.emplace_back(y1, x1, x2, 1);
xx.push_back(x1);
line.emplace_back(y2, x1, x2, -1);
xx.push_back(x2);
}
void pushup(int s, int t, int p) {
if (tag[p]) {
len[p] = xx[t] - xx[s] ;
} else if (s == t) {
len[p] = 0;
} else {
len[p] = len[p * 2] + len[p * 2 + 1];
}
}
void update(int l, int r, int flag, int s, int t, int p) {
if (l <= s && t <= r) {
tag[p] += flag;
pushup(s, t, p);
return;
}
int m = (s + t) / 2;
if (l < m) update(l, r, flag, s, m, p * 2);
if (r > m) update(l, r, flag, m, t, p * 2 + 1);
pushup(s, t, p);
}
void init() {
sort(xx.begin(), xx.end());
sort(line.begin(), line.end());
num = unique(xx.begin(), xx.end()) - xx.begin();
}
void work() {
init();
int pre = 0;
for (int i = 0; i < line.size(); i++) {
pre = len[1];
int l = lower_bound(xx.begin(), xx.begin() + num, line[i].lx) - xx.begin();
int r = lower_bound(xx.begin(), xx.begin() + num, line[i].rx) - xx.begin();
update(l, r, line[i].flag, 0, num - 1, 1);
C += abs(len[1] - pre);
}
}
i64 getlen() {
return C;
}
};