BZOJ 4520: [Cqoi2016]K远点对(k-d tree)

// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
#include<queue>
#define int long long 
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
using namespace std;
const int MAXN = 200001, INF = 1e9 + 10;
char buf[1 << 21], *p1 = buf, *p2 = buf;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, K;
priority_queue<int, vector<int>, greater<int> > q;
int root, WD, cur = 0;
#define ls(k) T[k].ls
#define rs(l) T[k].rs
struct Point {
    int x[2];
    bool operator < (const Point &rhs) const {
        return x[WD] < rhs.x[WD];
    }
}p[MAXN];
struct KDtree {
    int ls, rs, mi[2], mx[2];
    Point tp;
}T[MAXN];
inline int sqr(int x) {
    return x * x;
}
void update(int k) {
    for(int i = 0; i <= 1; i++) {
        T[k].mi[i] = T[k].mx[i] = T[k].tp.x[i];
        if(ls(k)) T[k].mi[i] = min(T[k].mi[i], T[ls(k)].mi[i]), T[k].mx[i] = max(T[k].mx[i], T[ls(k)].mx[i]);
        if(rs(k)) T[k].mi[i] = min(T[k].mi[i], T[rs(k)].mi[i]), T[k].mx[i] = max(T[k].mx[i], T[rs(k)].mx[i]);
    }
}
int Build(int l, int r, int wd) {
    if(l > r) return 0;
    WD = wd;
    int k = ++cur, mid = l + r >> 1;
    nth_element(p + l, p + mid, p + r + 1);
    T[k].tp = p[mid];
    T[k].ls = Build(l, mid - 1, wd ^ 1);
    T[k].rs = Build(mid + 1, r, wd ^ 1);
    update(k);
    return k;
}
int dis(Point a, Point b) {
    return sqr(a.x[0] - b.x[0]) + sqr(a.x[1] - b.x[1]);
}
int GetMaxDis(KDtree a, Point b) {
    int rt = 0;
    for(int i = 0; i <= 1; i++) 
        rt += sqr(max(abs(b.x[i] - a.mi[i]), abs(b.x[i] - a.mx[i])));
    return rt;
}
void Query(int k, Point a) {
    int tmp = q.top(), tmpdis = dis(T[k].tp, a);
    if(tmpdis > tmp) q.pop(), q.push(tmpdis);
    int disl = -INF, disr = -INF;
    if(ls(k)) disl = GetMaxDis(T[ls(k)], a);
    if(rs(k)) disr = GetMaxDis(T[rs(k)], a);
    if(disl > disr) {
        if(disl > q.top()) Query(ls(k), a);
        if(disr > q.top()) Query(rs(k), a);
    } 
    else {
        if(disr > q.top()) Query(rs(k), a);
        if(disl > q.top()) Query(ls(k), a);
    }
}
main() {
    #ifdef WIN32
    freopen("a.in", "r", stdin);
    #endif
    N =read(); K = read();
    for(int i = 1; i <= N; i++) 
        p[i].x[0] = read(), p[i].x[1] = read();
    root = Build(1, N, 0);
    for(int i = 1; i <= 2 * K; i++) 
        q.push(0);
    for(int i = 1; i <= N; i++) 
        Query(root, p[i]);
    printf("%lld", q.top());
}