Luogu

LOJ

分析

暴力就是维护一个大小为 $k$ 的小根堆,然后 $\mathcal{O}(n^2)$ 枚举。

考虑用 KD-Tree 优化。对于每个点在 KD-Tree 上递归,如果当当前矩形的最大距离比堆顶小则不可能更新答案,可以直接返回。

因为是每对点算了两遍所以堆的大小应为 $2k$,为了方便可以先插 $2k$ 个 $0$ 进去。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
#define re register
#define sqr(x) (1ll*(x)*(x))
using namespace std;
typedef long long ll;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,k;
priority_queue<ll,vector<ll>,greater<ll> > Q;

#define ls t[o].lc
#define rs t[o].rc
int D,tot=0,rt;
struct point { int x[2]; } p[N];
bool operator <(point a,point b) { return a.x[D]<b.x[D]; }
struct node { int mn[2],mx[2],lc,rc; point p; } t[N];
inline int newnode() { return ++tot; }
inline void pushup(int o) {
    for (re int i=0;i<2;++i) {
        t[o].mn[i]=t[o].mx[i]=t[o].p.x[i];
        if (ls) {
            t[o].mn[i]=min(t[o].mn[i],t[ls].mn[i]);
            t[o].mx[i]=max(t[o].mx[i],t[ls].mx[i]);
        }
        if (rs) {
            t[o].mn[i]=min(t[o].mn[i],t[rs].mn[i]);
            t[o].mx[i]=max(t[o].mx[i],t[rs].mx[i]);
        }
    }
}
inline int build(int l,int r,int d) {
    if (l>r) return 0;
    int o=newnode(),mid=(l+r)>>1;
    D=d,nth_element(p+l,p+mid,p+r+1),t[o].p=p[mid];
    ls=build(l,mid-1,d^1),rs=build(mid+1,r,d^1);
    pushup(o); return o;
}
inline ll dis(point a,point b) {
    return sqr(a.x[0]-b.x[0])+sqr(a.x[1]-b.x[1]);
}
inline ll maxdis(node o,point p) {
    ll res=0;
    res=max(res,dis(p,(point){o.mn[0],o.mn[1]}));
    res=max(res,dis(p,(point){o.mn[0],o.mx[1]}));
    res=max(res,dis(p,(point){o.mx[0],o.mn[1]}));
    res=max(res,dis(p,(point){o.mx[0],o.mx[1]}));
    return res;
}
inline void query(int o,point p) {
    if (dis(t[o].p,p)>Q.top()) Q.pop(),Q.push(dis(t[o].p,p));
    if (ls&&maxdis(t[ls],p)>Q.top()) query(ls,p);
    if (rs&&maxdis(t[rs],p)>Q.top()) query(rs,p);
}
#undef ls
#undef rs

int main() {
    n=read(),k=read();
    for (re int i=1;i<=n;++i) p[i].x[0]=read(),p[i].x[1]=read();
    for (re int i=1;i<=k<<1;++i) Q.push(0);
    rt=build(1,n,0);
    for (re int i=1;i<=n;++i) query(rt,p[i]);
    printf("%lld\n",Q.top());
    return 0;
}
最后修改:2020 年 02 月 25 日 12 : 06 PM