9482번: 가까운 만유인력

https://www.acmicpc.net/problem/9482


$O(nlgn+min(n^2,c))$ // c: 거리가 k이하인 쌍의 최댓값

(x,y,z) 좌표계에서 각 성분을 k 만큼씩마다 나누어 버킷을 만든다. 즉, 한 성분 구간의 크기가 l이면 (l/k)^3개의 버킷이 생길 것이다.
비둘기 집의 원리에 따라 하나의 버킷 안에는 최대 O(min(n,sqrt(c)))개의 점들이 있다.
또한 이렇게 나누면 각 점들은 자신이 속한 버킷과 인접한 버킷(대각 방향도 포함)에서만 쌍 후보를 찾아도 된다.
그 밖의 버킷에는 무조건 점들 쌍의 거리가 k이상이기 때문이다.
찾을 후보의 쌍 개수는 최대 O(min(n^2,c))가 된다.

해시, 자가 균형 이진 탐색 트리, 정렬 후 이진 검색(아래 소스) 등을 이용해 특정 버킷 안의 점을 찾을 수 있을 것이다.

#include<cstdio>
#include<algorithm>
#include<vector>
#define p(x) (long long)(x)*(x)
using namespace std;
int n, k;
vector<int> v[100000];
int main() {
    while (scanf("%d%d", &n, &k) && n) {
        int r = 0;
        for (int i = 0; i < n; i++) {
            v[i].resize(6);
            for (int j = 3; j < 6; j++) scanf("%d", &v[i][j]), v[i][j - 3] = (v[i][j] += 1e9) / k;
        }
        sort(v, v + n);
        for (int i = 0; i<n; i++) {
            for (int j = 0; j<27; j++) {
                vector<int> lv = { v[i][0] + j % 3 - 1,v[i][1] + j / 3 % 3 - 1,v[i][2] + j / 9 - 1 }, uv = lv;
                uv[2]++;
                int l = lower_bound(v, v + n, lv) - v,
                    u = upper_bound(v, v + n, uv) - v;
                for (; l < u; l++) r += p(v[l][3] - v[i][3]) + p(v[l][4] - v[i][4]) + p(v[l][5] - v[i][5]) < p(k);
            }
        }
        printf("%d\n", (r - n) / 2);
    }
    return 0;
}