题面

自己去\(LOJ\)上找

Sol

直接排序然后\(KDTree\)查询

然后发现\(TLE\)了

然后把点旋转一下，就过了。。

# include 
    
     # define IL inline# define RG register# define Fill(a, b) memset(a, b, sizeof(a))using namespace std;typedef long long ll;IL int Input(){    RG int x = 0, z = 1; RG char c = getchar();    for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;    for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);    return x * z;}const int maxn(3e5 + 5);const double eps(1e-3);const double alpha(acos(-1) / 5);const double cosa(cos(alpha));const double sina(sin(alpha));int n, ans[maxn], op, rt;struct Data{    double d[2], r;    int id;        IL int operator <(RG Data b) const{        return d[op] < b.d[op];    }} a[maxn];IL int Cmp(RG Data x, RG Data y){    return x.r != y.r ? x.r > y.r : x.id < y.id;}struct KDTree{    double d[2], mn[2], mx[2], r;    int ls, rs, id;} tr[maxn];IL void Chkmax(RG double &x, RG double y){    if(y > x) x = y;}IL void Chkmin(RG double &x, RG double y){    if(y < x) x = y;}IL void Update(RG int x){    tr[x].mn[0] = tr[x].mx[0] = tr[x].d[0];    tr[x].mn[1] = tr[x].mx[1] = tr[x].d[1];    RG int ls = tr[x].ls, rs = tr[x].rs;    if(ls){        Chkmin(tr[x].mn[0], tr[ls].mn[0]), Chkmin(tr[x].mn[1], tr[ls].mn[1]);        Chkmax(tr[x].mx[0], tr[ls].mx[0]), Chkmax(tr[x].mx[1], tr[ls].mx[1]);    }    if(rs){        Chkmin(tr[x].mn[0], tr[rs].mn[0]), Chkmin(tr[x].mn[1], tr[rs].mn[1]);        Chkmax(tr[x].mx[0], tr[rs].mx[0]), Chkmax(tr[x].mx[1], tr[rs].mx[1]);    }}IL int Build(RG int l, RG int r, RG int nop){    RG int x = (l + r) >> 1; op = nop;    nth_element(a + l, a + x, a + r + 1);    tr[x].d[0] = a[x].d[0], tr[x].d[1] = a[x].d[1];    tr[x].id = a[x].id, tr[x].r = a[x].r;    if(l < x) tr[x].ls = Build(l, x - 1, nop ^ 1);    if(r > x) tr[x].rs = Build(x + 1, r, nop ^ 1);    Update(x);    return x;}# define Sqr(x) ((x) * (x))IL int Check(RG int x, RG Data p){    RG double x1 = tr[x].d[0], y1 = tr[x].d[1], x2 = p.d[0], y2 = p.d[1], r1 = tr[x].r, r2 = p.r;    return Sqr(x1 - x2) + Sqr(y1 - y2) - eps <= Sqr(r1 + r2);}IL int Cut(RG int x, RG Data p){    RG double x2 = p.d[0], y2 = p.d[1], r = p.r + p.r;    if(x2 + r + eps < tr[x].mn[0]) return 1;    if(y2 + r + eps < tr[x].mn[1]) return 1;    if(x2 - r > tr[x].mx[0] + eps) return 1;    if(y2 - r > tr[x].mx[1] + eps) return 1;    return 0;}IL void Modify(RG int x, RG Data p){    if(Cut(x, p)) return;    if(!ans[tr[x].id] && Check(x, p)) ans[tr[x].id] = p.id;    if(tr[x].ls) Modify(tr[x].ls, p);    if(tr[x].rs) Modify(tr[x].rs, p);}int main(){    n = Input();    for(RG int i = 1; i <= n; ++i){        RG double x = Input(), y = Input(), r = Input();        a[i] = (Data){x * cosa - y * sina, x * sina + y * cosa, r, i};    }    rt = Build(1, n, 0), sort(a + 1, a + n + 1, Cmp);    for(RG int i = 1; i <= n; ++i)        if(!ans[a[i].id]) Modify(rt, a[i]);    for(RG int i = 1; i <= n; ++i) printf("%d ", ans[i]);    return 0;}