校内赛 三维盒子

题目描述

依次加入 $n$ 个长方体，所有长方体的每条棱都与坐标轴平行，第 $i$ 个长方体的左上角的坐标为 $(x,y,z)$，所有长方体的长度都为 $dx$，宽度都为 $dy$，高度都为 $dz$

求在依次加入长方体的过程中，最早在什么时候出现两个长方体有公共点，两个长方体有公共点当且仅当 $|x_i-x_j|\le dx,|y_i-y_j|\le dy,|z_i-z_j|\le dz$ 都满足，若所有长方体都加入后依然没有重叠，输出 $0$

Solution

看起来好像需要 $k-d~tree$，实际上并不需要

我们考虑将所有长方体缩到 $(\lfloor\frac{x}{dx}\rfloor,\lfloor\frac{y}{dy}\rfloor,\lfloor\frac{z}{dz}\rfloor)$ ，首先如果同一个位置有多个点那么一定有公共点，否则只有这个坐标周围的 $27$ 个点可能会与它有公共点，判断一下即可

时间复杂度 $O(27n\log n)$

#include <iostream>
#include <map>
#include <tuple>
#define maxn 100010
using namespace std;

int n, dx, dy, dz;

map<tuple<int, int, int>, tuple<int, int, int>> mp;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> dx >> dy >> dz;
    for (int o = 1; o <= n; ++o) { 
        int x, y, z; cin >> x >> y >> z; 
        tuple<int, int, int> t(x / dx, y / dy, z / dz);
        for (int i = -1; i <= 1; ++i)
            for (int j = -1; j <= 1; ++j)
                for (int k = -1; k <= 1; ++k) {
                    tuple<int, int, int> t = make_tuple(x / dx + i, y / dy + j, z / dz + k); 
                    if (mp.find(t) != mp.end()) {
                        int u, v, w; tie(u, v, w) = mp[t];
                        if (abs(x - u) <= dx && abs(v - y) <= dy && abs(w - z) <= dz)
                            return cout << o << "\n", 0;
                    }
                }
        mp[t] = { x, y, z };
    }
    cout << 0 << "\n"; 
    return 0;
}