qwq纪念AC450

一开始想这个题想复杂了。

首先，正解的做法是比较麻烦的。

qwqq

那么就不如来一点暴力的东西，看到平面上点的距离的题，不难想到\(KD-Tree\)

我们用类似平面最近点对那个题一样的维护方式，对于一个子树内部，分别维护每一个维度的最大值和最小值，还有半径的最大值。

然后\(sort\)一遍，从半径大到小依次\(query\)，每次\(query\)的时候，对于当前点，合法的条件是他和目标点的距离要小于等于两个圆的半径的和。

那么对于子树的估价函数，我们默认如果当前目标点的当前维度的范围是\(mn-mx\)之间的话，距离就是\(0\)，否则取一个最短距离，然后和上述要求一样的比较方式。进行剪枝。

这样就能直接通过洛谷的数据了，但是由于\(loj\)的数据比较强，所以还需要将原来的点绕着一个点旋转一下。

那么假设我们旋转的角度是\(\phi\)

那么我们需要将原来那两个坐标乘上一个矩阵

cos -sin

sin cos

直接上代码了

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<vector>

#include<queue>

#include<cmath>

#include<map>

#include<set>

#define pb push_back

#define mk make_pair

#define ll long long

#define lson ch[x][0]

#define rson ch[x][1]

#define double long double

#define int long long

using namespace std;

inline int read()

{

  int x=0,f=1;char ch=getchar();

  while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}

  while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

  return x*f;

}

const int maxn = 4e5+1e2;

const double phi = 1.04719755116;

const double eps = 1e-4;

struct KD{

	double d[2],mx[2],mn[2];

	double bj,mr;

	int l,r;

	int num;

};

KD now,t[maxn];

int root,ymh,n,m;

int ans[maxn];

struct Node{

  double x,y;

  double r;

  int num;

};

Node a[maxn];

bool cmp(Node a,Node b)

{

	if (a.r==b.r) return a.num<b.num;

	return a.r>b.r;

}

bool operator <(KD a,KD b)

{

	return a.d[ymh]<b.d[ymh];

}

void up(int root)

{

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

	{

		if (t[root].l) t[root].mn[i]=min(t[root].mn[i],t[t[root].l].mn[i]);

		if (t[root].l) t[root].mx[i]=max(t[root].mx[i],t[t[root].l].mx[i]);

		if (t[root].l) t[root].mr=max(t[root].mr,t[t[root].l].mr);

		if (t[root].r) t[root].mr=max(t[root].mr,t[t[root].r].mr);

		if (t[root].r) t[root].mn[i]=min(t[root].mn[i],t[t[root].r].mn[i]);

		if (t[root].r) t[root].mx[i]=max(t[root].mx[i],t[t[root].r].mx[i]);

	}

}

void build(int &x,int l,int r,int dd)

{

	ymh = dd;

	int mid = l+r >> 1;

	x=mid;

	nth_element(t+l,t+mid,t+r+1);

	for (int i=0;i<=1;i++) t[x].mn[i]=t[x].mx[i]=t[x].d[i];

	t[x].mr=t[x].bj;

	if (l<x) build(t[x].l,l,mid-1,dd^1);

	if (x<r) build(t[x].r,mid+1,r,dd^1);

	up(x);

}

inline double getdis(int x)

{

	double ans=0;

	for (int i=0;i<=1;i++) ans=ans+(t[x].d[i]-now.d[i])*(t[x].d[i]-now.d[i]);

	return ans;

}

inline double calc(int x)

{

	double ans=0;

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

	{

	  double tmp=0;

	  if (now.d[i]>=t[x].mn[i] && now.d[i]<=t[x].mx[i]) tmp=0;

	  else tmp=min((t[x].mn[i]-now.d[i])*(t[x].mn[i]-now.d[i]),(t[x].mx[i]-now.d[i])*(t[x].mx[i]-now.d[i]));

	  ans=ans+tmp;

    }

	return ans;

}

void query(int x)

{

	//cout<<now.num<<endl;

	//cout<<x<<" "<<t[x].l<<" "<<t[x].r<<" "<<t[x].mr<<" "<<t[x].d[1]<<endl;;

	if (!x) return;

	double d = getdis(x);

	double d1 = calc(t[x].l);

	double d2 = calc(t[x].r);

	//cout<<d1<<" "<<(t[t[x].l].mr+now.bj)<<" "<<d2<<endl;

	if (!ans[t[x].num] && (t[x].bj+now.bj)*(t[x].bj+now.bj)-d>=-eps) ans[t[x].num]=now.num;

	if ((t[t[x].l].mr+now.bj)*(t[t[x].l].mr+now.bj)-d1>=-eps) query(t[x].l);

	if ((t[t[x].r].mr+now.bj)*(t[t[x].r].mr+now.bj)-d2>=-eps) query(t[x].r);

}

signed main()

{

  n=read();

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

  {

  	 double x=read(),y=read(),r=read();

  	 double tmp = x;

	 x=cos(phi)*x-sin(phi)*y;

	 y=sin(phi)*tmp+cos(phi)*y;

	 t[i].num=i;

	 t[i].d[0]=x;

	 t[i].d[1]=y;

	 t[i].bj=r;

	 a[i].x=x;

	 a[i].y=y;

	 a[i].num=i;

	 a[i].r=r;

	 //printf("%.2lf %.2lf %.2lf\n",x,y,r);

	 //cout<<endl;

  }

  build(root,1,n,0);

  //cout<<"********"<<endl;

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

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

  {

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

  	 now.d[0]=a[i].x;

  	 now.d[1]=a[i].y;

  	 now.bj=a[i].r;

  	 now.num=a[i].num;

  	 query(root);

  	 //out<<"*******"<<endl;

  }

  for (int i=1;i<=n;i++) cout<<ans[i]<<" ";

  return 0;

}