hdu 3642(扫描线)

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

#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 3642(扫描线)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。