Overview

给出平面上两两不重合的$n$个整点, 求每个点到它在其他$n-1$个点的最近临点的欧几里得距离的平方.

Solution

k-d tree 模板题.

关于k-d tree, 见这篇博客.

Implementation

#include <bits/stdc++.h>

#define lson id<<1

#define rson id<<1|1

#define sqr(x) (x)*(x)

using namespace std;

using LL=long long;

const int N=1e5+5;

// K-D tree: a special case of binary space partitioning trees

int DIM=2, idx;

struct Node{

    LL key[2];

    bool operator<(const Node &rhs)const{

        return key[idx]<rhs.key[idx];

    }

    void read(){

        for(int i=0; i<DIM; i++)

            scanf("%lld", key+i);

    }

    LL dis2(const Node &rhs)const{

        LL res=0;

        for(int i=0; i<DIM; i++)

            res+=sqr(key[i]-rhs.key[i]);

        return res;

    }

}p[N], _p[N];

Node a[N<<2];   // K-D tree

bool f[N<<2];

// [l, r)

void build(int id, int l, int r, int dep){

    if(l==r) return;    // error-prone

    f[id]=true, f[lson]=f[rson]=false;

    // select axis based on depth so that axis cycles through all valid values

    idx=dep%DIM;

    int mid=l+r>>1;

    // sort point list and choose median as pivot element

    nth_element(p+l, p+mid, p+r);

    a[id]=p[mid];

    build(lson, l, mid, dep+1);

    build(rson, mid+1, r, dep+1);

}

LL mi;

void query(const Node &p, int id, int dep){

    int dim=dep%DIM;

    int x=lson, y=rson;

    // left: <, right >=

    if(p.key[dim]>=a[id].key[dim])

        swap(x, y);

    if(f[x]) query(p, x, dep+1);

    LL cur=p.dis2(a[id]);

    if(cur && cur<mi) mi=cur;

    if(f[y] && sqr(a[id].key[dim]-p.key[dim])<mi)

        query(p, y, dep+1);

}

int main(){

    int T;

    scanf("%d", &T);

    for(int n; T--; ){

        scanf("%d", &n);

        for(int i=0; i<n; i++){

            p[i].read();

            _p[i]=p[i]; //error-prone

        }

        build(1, 0, n, 0);

        for(int i=0; i<n; i++){

            mi=LLONG_MAX;

            query(_p[i], 1, 0);  //error-prone

            printf("%lld\n", mi);

        }

    }

    return 0;

}