LOJ 2586 「APIO2018」选圆圈—

只会 19 分的暴力。

y 都相等，仍然按直径从大到小做。如果当前圆没有被删除，那么用线段树把 [ x-r , x+r ] 都打上它的标记。

看当前圆有没有被删除，只要看 x-r 和 x+r 两个位置上的标记就行了。因为被删除的话当前圆的直径更小，有相交的话， x-r 或 x+r 一定在对方内部。可以 x-r 和 x+r 分别在两个圆内部，看看哪个更大即可。

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

#define ls Ls[cr]

#define rs Rs[cr]

using namespace std;

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return fx?ret:-ret;

}

ll Sqr(int x){return (ll)x*x;}

int Mx(int a,int b){return a>b?a:b;}

int Mn(int a,int b){return a<b?a:b;}

const int N=3e5+;

int n,ans[N];

struct Node{

  int x,y,r,id;

}a[N];

namespace S1{

  bool cmp(Node u,Node v)

  {return u.r==v.r?u.id<v.id:u.r>v.r;}

  bool chk(Node u,Node v)

  { return Sqr(u.r+v.r)>=Sqr(u.x-v.x)+Sqr(u.y-v.y);}

  void solve()

  {

    sort(a+,a+n+,cmp);

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

      {

    int cr=a[i].id; if(ans[cr])continue; ans[cr]=cr;

    for(int j=i+;j<=n;j++)

      if(chk(a[i],a[j])&&!ans[a[j].id])ans[a[j].id]=cr;//!ans[]!!!

      }

    for(int i=;i<=n;i++)printf("%d ",ans[i]);puts("");

  }

}

namespace S2{

  const int M=N<<;

  int dy[N],tp[N<<],m,c0[N],c1[N],tot,Ls[M],Rs[M],tg[M];

  bool cmp(Node u,Node v){return u.r==v.r?u.id<v.id:u.r>v.r;}

  void build(int l,int r,int cr)

  {

    if(l==r)return; int mid=l+r>>;

    ls=++tot; build(l,mid,ls);

    rs=++tot; build(mid+,r,rs);

  }

  int qry(int l,int r,int cr,int p)

  {

    if(l==r)return tg[cr]; int mid=l+r>>;

    if(p<=mid)return tg[cr]|qry(l,mid,ls,p);

    return tg[cr]|qry(mid+,r,rs,p);

  }

  void mdfy(int l,int r,int cr,int L,int R,int k)

  {

    if(l>=L&&r<=R){tg[cr]=k;return;}

    int mid=l+r>>;

    if(L<=mid)mdfy(l,mid,ls,L,R,k);

    if(mid<R)mdfy(mid+,r,rs,L,R,k);

  }

  void solve()

  {

    sort(a+,a+n+,cmp);

    for(int i=;i<=n;i++)dy[i]=a[i].id;

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

      {tp[++m]=a[i].x-a[i].r; tp[++m]=a[i].x+a[i].r;}

    sort(tp+,tp+m+); m=unique(tp+,tp+m+)-tp-;

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

      {

    c0[i]=lower_bound(tp+,tp+m+,a[i].x-a[i].r)-tp;

    c1[i]=lower_bound(tp+,tp+m+,a[i].x+a[i].r)-tp;

      }

    tot=; build(,m,);

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

      {

    int d0=qry(,m,,c0[i]), d1=qry(,m,,c1[i]), cr=a[i].id;

    if(d0&&d1){ans[cr]=dy[Mn(d0,d1)];continue;}

    if(d0||d1){ans[cr]=dy[d0|d1];continue;}

    ans[cr]=cr; mdfy(,m,,c0[i],c1[i],i);

      }

    for(int i=;i<=n;i++)printf("%d ",ans[i]);puts("");

  }

}

int main()

{

  n=rdn();

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

    a[i].x=rdn(),a[i].y=rdn(),a[i].r=rdn(),a[i].id=i;

  if(n<=){S1::solve();return ;}

  bool fg=;

  for(int i=;i<=n;i++)if(a[i].y){fg=;break;}

  if(!fg){S2::solve();return ;}

  return ;

}

正解竟然是 KD 树。

用矩形来表示一个圆，把 KD 树建出来。在删除一个圆的时候在 KD 树上找和它相交的圆。矩形就是估价。

可以把坐标轴旋转一定角度。自己旋转了 60 度。那么原来的 x 和 y 算一下的话会变成 \( \frac{x}{cos\alpha} + ( y - \frac{x}{cos\alpha} * sin\alpha )sin\alpha , ( y - \frac{x}{cos\alpha}*sin\alpha )cos\alpha ) \) 。

eps 设成 1e-8 会 WA ， 1e-3 就行了。也不知何故。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define ls c[cr][0]

#define rs c[cr][1]

#define db double

using namespace std;

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return fx?ret:-ret;

}

db Mn(db a,db b){return a<b?a:b;}

db Mx(db a,db b){return a>b?a:b;}

db Sqr(db x){return x*x;}

const int N=3e5+;

const db eps=1e-,pi=acos(-),nc=cos(pi/),ns=sin(pi/);

int dcmp(db x){ if(x<-eps)return -;if(x>eps)return ;return ;}

int n,tot,c[N][],ans[N]; bool fx;

struct Dt{ db x[];int r,id;}a[N];

struct Node{

  db x[],y[];Dt a;

}p[N];

bool cmp(Dt u,Dt v){return u.x[fx]<v.x[fx];}

bool cmp2(Dt u,Dt v){return u.r==v.r?u.id<v.id:u.r>v.r;}

void pshp(int cr)

{

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

    {p[cr].x[i]=p[cr].a.x[i]-p[cr].a.r;

      p[cr].y[i]=p[cr].a.x[i]+p[cr].a.r;}

  if(ls)

    {

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

    {p[cr].x[i]=Mn(p[cr].x[i],p[ls].x[i]);

      p[cr].y[i]=Mx(p[cr].y[i],p[ls].y[i]);}

    }

  if(rs)

    {

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

    {p[cr].x[i]=Mn(p[cr].x[i],p[rs].x[i]);

      p[cr].y[i]=Mx(p[cr].y[i],p[rs].y[i]);}

    }

}

void build(int l,int r,int cr,bool nw)

{

  int mid=l+r>>; fx=nw;nth_element(a+l,a+mid,a+r+,cmp);

  p[cr].a=a[mid];

  if(l<mid){ ls=++tot;build(l,mid-,ls,!nw);}

  if(mid<r){ rs=++tot;build(mid+,r,rs,!nw);}

  pshp(cr);

}

bool Out(int cr,db x[],int r)

{

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

    {

      if(dcmp(p[cr].x[i]-(x[i]+r))>)return true;

      if(dcmp((x[i]-r)-p[cr].y[i])>)return true;

    }

  return false;

}

bool itr(Dt u,Dt v)

{return dcmp(Sqr(u.r+v.r)-Sqr(u.x[]-v.x[])-Sqr(u.x[]-v.x[]))>=;}

void mdfy(int cr,Dt k)

{

  if(Out(cr,k.x,k.r))return;

  if(!ans[p[cr].a.id]&&itr(p[cr].a,k))ans[p[cr].a.id]=k.id;

  if(ls)mdfy(ls,k); if(rs)mdfy(rs,k);

}

int main()

{

  n=rdn();

  for(int i=,x,y;i<=n;i++)

    {

      x=rdn(); y=rdn(); a[i].r=rdn();a[i].id=i;

      db t0=x/nc, t1=y-x/nc*ns;

      a[i].x[]=t0+t1*ns; a[i].x[]=t1*nc;

    }

  tot=;build(,n,,); sort(a+,a+n+,cmp2);

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

    {

      if(ans[a[i].id])continue;

      mdfy(,a[i]);

    }

  for(int i=;i<=n;i++)printf("%d ",ans[i]);puts("");

  return ;

}

巴特西

LOJ 2586 「APIO2018」选圆圈——KD树

最新文章

热门文章