[APIO2018]Circle selection

kd-tree

题面

在平面上，有$n$个圆，记为$c_1,c_2,...,c_n$。我们尝试对这些圆运行这个算法：

• 找到这些圆中半径最大的。如果有多个半径最大的圆，选择编号最小的。记为$c_i$。
• 删除$c_i$及与其相交的所有圆。
• 重复上面两个步骤直到所有的圆都被删除。

当$c_i$被删除时，若循环中第$1$步选择的圆是$c_j$，我们说$c_i$被$c_j$删除。对于每个圆，求出它是被哪一个圆删除的。

解析

题目太火，正解无从想象，准备暴力骗分。

什么东西能够快速维护平面上的东西？
二维树状数组、二维线段树？蒟蒻不会。。。
于是就只剩$kd-tree$了。

$kd-tree$本质上就是一个经过优化的暴力（优化在缩小搜索范围，只对近邻进行搜索），是靠剪枝吃饭的。
我们可以用它维护每个圆在$x,y$轴的范围，即$[x-r,x+r],[y-r,y+r]$。
这样相当于维护一个矩形，但是并不会漏掉答案，并且维护起来很方便。
于是建完树后，从前往后对每个圆通过$kd-tree$暴力统计答案即可。

然而这样只有$42pts$，我们需要更多剪枝。
可以注意到，如果搜到一个圆，在当前统计答案的圆的（矩形）范围之外，这个圆显然不会对答案有贡献，可以跳过。

于是就可以通过洛谷数据了？然而$loj$上跑不过最后一档。
把每个点转一个角度就可以$AC$。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define re register
#define il inline
#define ll long long
#define db double
#define ls t[k].l
#define rs t[k].r
#define eps 1e-6
#define pf(x) ((db)(1.0)*(x)*(x))
#define max(a,b) (((a)>(b)?(a):(b)))
#define min(a,b) (((a)<(b)?(a):(b)))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=3e5+100;
int now,n,rt,ans[N];
struct dat
{
  int d[2],r,id;
  bool operator < (const dat &o) const {return d[now]<o.d[now];}
}a[N];
struct node
{
  dat a;
  int l,r,mn[2],mx[2];
}t[N];
il int gi()
{
   re int x=0,t=1;
   re char ch=getchar();
   while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
   if(ch=='-') t=-1,ch=getchar();
   while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
   return x*t;
}
il void cmax(re int &x,re int y){x=max(x,y);}
il void cmin(re int &x,re int y){x=min(x,y);}
il bool cmp(dat x,dat y){return (x.r==y.r)?(x.id<y.id):(x.r>y.r);}
struct kd_tree
{
  il void upd(re int k,re int p)
  {
    cmin(t[k].mn[0],t[p].mn[0]);cmax(t[k].mx[0],t[p].mx[0]);
    cmin(t[k].mn[1],t[p].mn[1]);cmax(t[k].mx[1],t[p].mx[1]);
  }
  il void pushup(re int k)
  {
        re int x=t[k].a.d[0],y=t[k].a.d[1],r=t[k].a.r;
    t[k].mn[0]=x-r;t[k].mx[0]=x+r;
    t[k].mn[1]=y-r;t[k].mx[1]=y+r;
    if(ls) upd(k,ls);if(rs) upd(k,rs);
  }
  il void Build(re int &k,re int l,re int r,re int tag)
  {
    re int mid=l+r>>1;now=tag;
    nth_element(a+l,a+mid,a+r+1);k=mid;
    t[k].a=a[mid];
    if(l<mid) Build(ls,l,mid-1,tag^1);else ls=0;
    if(mid<r) Build(rs,mid+1,r,tag^1);else rs=0;
    pushup(k);
  }
  il int check(re int k,re dat A)
  {
    re int x=A.d[0],y=A.d[1],r=A.r+t[k].a.r,xx=t[k].a.d[0],yy=t[k].a.d[1];
    return pf(1ll*x-xx)+pf(1ll*y-yy)-eps<=pf(r);
  }
  il int far(re int k,re dat A)
  {
    re int x=A.d[0],y=A.d[1],r=A.r;
    if(x+r<t[k].mn[0]) return 1;
    if(y+r<t[k].mn[1]) return 1;
    if(x-r>t[k].mx[0]) return 1;
    if(y-r>t[k].mx[1]) return 1;
    return 0;
  }
  il void Query(re int k,re dat A)
  {
    if(far(k,A)) return;
    if(!ans[t[k].a.id]&&check(k,A)) ans[t[k].a.id]=A.id;
    if(ls) Query(ls,A);if(rs) Query(rs,A);
  }
}kd;
int main()
{
  n=gi();
  fp(i,1,n)
    {
      a[i].d[0]=gi();a[i].d[1]=gi();a[i].r=gi();a[i].id=i;
    }
  kd.Build(rt,1,n,0);
  sort(a+1,a+1+n,cmp);
  fp(i,1,n) if(!ans[a[i].id]) kd.Query(rt,a[i]);
  fp(i,1,n) printf("%d ",ans[i]);puts("");
  return 0;
}