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

Time Limit: 30 Sec Memory Limit: 512 MB
Submit: 1162 Solved: 618
[Submit][Status][Discuss]

Description

已知平面内 N 个点的坐标，求欧氏距离下的第 K 远点对。

Input

输入文件第一行为用空格隔开的两个整数 N， K。接下来 N 行，每行两个整数 X,Y，表示一个点

的坐标。1 < = N < = 100000， 1 < = K < = 100， K < = N*(N−1)/2 ， 0 < = X, Y < 2^31。

Output

输出文件第一行为一个整数，表示第 K 远点对的距离的平方（一定是个整数）。

Sample Input

10 5
0 0
0 1
1 0
1 1
2 0
2 1
1 2
0 2
3 0
3 1

Sample Output

HINT

Source

自己yy了一波，过了样例就A了hhh

考虑到$k$很小，因此我们可以维护一个$2*k$个点的小根堆去维护每个点对(每个点对会被统计两次)

然后在K-D tree上暴力，如果当前点对的距离比堆顶的距离大，就把堆顶删除，然后把当前点加入

时间复杂度$O(n \sqrt(n))?$

// 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 = , INF = 1e9 + ;

char buf[ << ], *p1 = buf, *p2 = buf;

inline int read() {

    char c = getchar(); int x = , f = ;

    while(c < '' || c > '') {if(c == '-') f = -; c = getchar();}

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * f;

}

int N, K;

priority_queue<int, vector<int>, greater<int> > q;

int root, WD, cur = ;

#define ls(k) T[k].ls

#define rs(l) T[k].rs

struct Point {

    int x[];

    bool operator < (const Point &rhs) const {

        return x[WD] < rhs.x[WD];

    }

}p[MAXN];

struct KDtree {

    int ls, rs, mi[], mx[];

    Point tp;

}T[MAXN];

inline int sqr(int x) {

    return x * x;

}

void update(int k) {

    for(int i = ; i <= ; 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 ;

    WD = wd;

    int k = ++cur, mid = l + r >> ;

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

    T[k].tp = p[mid];

    T[k].ls = Build(l, mid - , wd ^ );

    T[k].rs = Build(mid + , r, wd ^ );

    update(k);

    return k;

}

int dis(Point a, Point b) {

    return sqr(a.x[] - b.x[]) + sqr(a.x[] - b.x[]);

}

int GetMaxDis(KDtree a, Point b) {

    int rt = ;

    for(int i = ; i <= ; 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 = ; i <= N; i++)

        p[i].x[] = read(), p[i].x[] = read();

    root = Build(, N, );

    for(int i = ; i <=  * K; i++)

        q.push();

    for(int i = ; i <= N; i++)

        Query(root, p[i]);

    printf("%lld", q.top());

}

秒客网