Luogu

LOJ

分析

暴力就是把所有圆排序后直接 $\mathcal{O}(n^2)$ 模拟。

考虑用 KD-Tree 优化模拟过程。

我们把每个圆看作它的外接矩形，然后对于当前删去的圆在 KD-Tree 上递归，如果圆与矩形没有交则不会更新，可以直接返回。

然后建树时按方差选维度就可以过了。

代码

// ===================================
//   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;

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=300000+10;

int n,ans[N];

#define ls t[o].lc
#define rs t[o].rc
int D,tot=0,rt;
struct point { int x[2],r,id; } p[N];
bool operator <(point a,point b) { return a.x[D]<b.x[D]; }
struct node { int mn[2],mx[2],lc,rc,sz; 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].p.x[i]-t[o].p.r;
        t[o].mx[i]=t[o].p.x[i]+t[o].p.r;
        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]);
        }
    }
    t[o].sz=t[ls].sz+t[rs].sz+1;
}
inline int getd(int l,int r) {
    double s[2]={0,0};
    for (re int i=0;i<2;++i) {
        double ave=0;
        for (re int j=l;j<=r;++j) ave+=p[j].x[i];
        ave/=(r-l+1);
        for (re int j=l;j<=r;++j) s[i]+=(p[j].x[i]-ave)*(p[j].x[i]-ave);
    }
    return s[0]<s[1];
}
inline int build(int l,int r) {
    if (l>r) return 0;
    int o=newnode(),mid=(l+r)>>1;
    D=getd(l,r),nth_element(p+l,p+mid,p+r+1),t[o].p=p[mid];
    ls=build(l,mid-1),rs=build(mid+1,r);
    pushup(o); return o;
}
inline int out(node t,point p) {
    for (re int i=0;i<2;++i)
        if (p.x[i]+p.r<t.mn[i]||p.x[i]-p.r>t.mx[i]) return 1;
    return 0;
}
inline int inter(point a,point b) {
    return sqr(a.x[0]-b.x[0])+sqr(a.x[1]-b.x[1])<=sqr(a.r+b.r);
}
inline void query(int o,point p) {
    if (!ans[t[o].p.id]&&inter(p,t[o].p)) ans[t[o].p.id]=p.id;
    if (ls&&t[ls].sz&&!out(t[ls],p)) query(ls,p);
    if (rs&&t[rs].sz&&!out(t[rs],p)) query(rs,p);
    t[o].sz=t[ls].sz+t[rs].sz+!ans[t[o].p.id];
}
#undef ls
#undef rs

inline int cmp(point a,point b) {
    return a.r!=b.r?a.r>b.r:a.id<b.id;
}

int main() {
    n=read();
    for (re int i=1;i<=n;++i)
        p[i].x[0]=read(),p[i].x[1]=read(),p[i].r=read(),p[i].id=i;
    rt=build(1,n);
    sort(p+1,p+n+1,cmp);
    for (re int i=1;i<=n;++i) if (!ans[p[i].id]) query(rt,p[i]);
    for (re int i=1;i<=n;++i) printf("%d%c",ans[i]," \n"[i==n]);
    return 0;
}