我是靠谱客的博主 潇洒柠檬,这篇文章主要介绍hdu 3642(扫描线),现在分享给大家,希望可以做个参考。

题意:有n个立方体,给出每个立方体的左下角坐标和右上角坐标,问至少三个立方体相交的体积和。
题解:刚做了一个平面的,其实原理一样,都是用线段树维护区间内不覆盖、覆盖一次、覆盖两次、覆盖三次的长度,然后区间合并仔细写就行了,因为z轴的取整范围最多到500,可以直接把所有z坐标保存排序然后枚举每小段z轴,把所有包含这段的立方体用扫描线处理,转化为平面问题,每次的计算的面积结果乘这小段z轴长度就是体积。

复制代码
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
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <map> using namespace std; const int N = 2005; struct Line { int lx, rx, h; int flag; Line(int a, int b, int c, int d):lx(a), rx(b), h(c), flag(d) {} bool operator < (const Line &a) const { return h < a.h; } }; int n, flag[N << 2], cube[N][6]; int tree[4][N << 2]; vector<int> a, b; vector<Line> line; map<int, int> mp; void pushup(int k, int left, int right) { if (flag[k] > 2) { tree[3][k] = tree[0][k]; tree[2][k] = tree[1][k] = 0; } else if (flag[k] == 2) { if (left + 1 == right) { tree[2][k] = tree[0][k]; tree[1][k] = tree[3][k] = 0; } else { tree[3][k] = tree[3][k * 2] + tree[3][k * 2 + 1] + tree[2][k * 2] + tree[2][k * 2 + 1] + tree[1][k * 2] + tree[1][k * 2 + 1]; tree[2][k] = tree[0][k] - tree[3][k]; tree[1][k] = 0; } } else if (flag[k] == 1) { if (left + 1 == right) { tree[1][k] = tree[0][k]; tree[2][k] = tree[3][k] = 0; } else { tree[3][k] = tree[3][k * 2] + tree[3][k * 2 + 1] + tree[2][k * 2] + tree[2][k * 2 + 1]; tree[2][k] = tree[1][k * 2] + tree[1][k * 2 + 1]; tree[1][k] = tree[0][k] - tree[3][k] - tree[2][k]; } } else { if (left + 1 == right) tree[3][k] = tree[2][k] = tree[1][k] = 0; else { tree[3][k] = tree[3][k * 2] + tree[3][k * 2 + 1]; tree[2][k] = tree[2][k * 2] + tree[2][k * 2 + 1]; tree[1][k] = tree[1][k * 2] + tree[1][k * 2 + 1]; } } } void build(int k, int left, int right) { tree[0][k] = a[right] - a[left]; tree[1][k] = tree[2][k] = tree[3][k] = flag[k] = 0; if (left + 1 != right) { int mid = (left + right) / 2; build(k * 2, left, mid); build(k * 2 + 1, mid, right); } } void modify(int k, int left, int right, int l, int r, int v) { if (l <= left && right <= r) { flag[k] += v; pushup(k, left, right); return; } int mid = (left + right) / 2; if (l < mid) modify(k * 2, left, mid, l, r, v); if (r > mid) modify(k * 2 + 1, mid, right, l, r, v); pushup(k, left, right); } int main() { int t, cas = 1; scanf("%d", &t); while (t--) { a.clear(), b.clear(), mp.clear(); scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d%d%d%d%d%d", &cube[i][0], &cube[i][1], &cube[i][2], &cube[i][3], &cube[i][4], &cube[i][5]); a.push_back(cube[i][0]); a.push_back(cube[i][3]); b.push_back(cube[i][2]); b.push_back(cube[i][5]); } if (n < 3) { printf("Case %d: 0n", cas++); continue; } sort(a.begin(), a.end()); a.erase(unique(a.begin(), a.end()), a.end()); sort(b.begin(), b.end()); b.erase(unique(b.begin(), b.end()), b.end()); int sz = a.size(), sz2 = b.size(); for (int i = 0; i < sz; i++) mp[a[i]] = i; build(1, 0, sz - 1); long long res = 0; for (int i = 0; i < sz2 - 1; i++) { line.clear(); for (int j = 0; j < n; j++) { if (cube[j][2] <= b[i] && cube[j][5] >= b[i + 1]) { line.push_back(Line(cube[j][0], cube[j][3], cube[j][1], 1)); line.push_back(Line(cube[j][0], cube[j][3], cube[j][4], -1)); } } sort(line.begin(), line.end()); int sz3 = line.size(); for (int j = 0; j < sz3; j++) { if (j != 0) res += (b[i + 1] - b[i]) * (line[j].h - line[j - 1].h) * (long long)tree[3][1]; modify(1, 0, sz - 1, mp[line[j].lx], mp[line[j].rx], line[j].flag); } } printf("Case %d: %lldn", cas++, res); } return 0; }

最后

以上就是潇洒柠檬最近收集整理的关于hdu 3642(扫描线)的全部内容,更多相关hdu内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(112)

评论列表共有 0 条评论

立即
投稿
返回
顶部