#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define int long long
#define itr ::iterator
typedef pair<int,int> pii;
const int MAX=5e5;
int N,x_,y_,r_,R_cur,R_next,order[MAX],par[MAX];
struct circle
{
int X;
int Y;
int R;
int ind;
init(int X_,int Y_,int R_,int ind_)
{
X=X_;
Y=Y_;
R=R_;
ind=ind_;
}
} arr[MAX],lol[MAX];
bool operator<(circle F,circle S)
{
if(F.X==S.X)
return F.Y<S.Y;
return F.X<S.X;
}
bool cmp(int F,int S)
{
if(lol[F].R==lol[S].R)
return lol[F].ind<lol[S].ind;
return lol[F].R>lol[S].R;
}
bool ok(int F,int S)
{
return (lol[F].X-lol[S].X)*(lol[F].X-lol[S].X)+(lol[F].Y-lol[S].Y)*(lol[F].Y-lol[S].Y)<=(lol[F].R+lol[S].R)*(lol[F].R+lol[S].R);
}
void init_()
{
R_cur=R_next;
R_next/=2;
for(int A=1;A<=N;A++)
arr[A].init(lol[A].X/R_cur,lol[A].Y/R_cur,lol[A].R,A);
sort(arr+1,arr+N+1);
return ;
}
void solve(int ind)
{
int tem;
int pos_x=arr[ind].X;
int pos_y=arr[ind].Y;
par[ind]=ind;
for(int cur_x=pos_x-2;cur_x<=pos_x+2;cur_x++)
{
tem=lower_bound(arr+1,arr+N+1,(circle){cur_x,pos_y-2,0,0})-arr;
while(tem<=N and arr[tem].X==cur_x and arr[tem].Y<=pos_y+2)
{
//cout<<arr[tem].ind<<" "<<ind<<"\n";
if(par[arr[tem].ind])
{
tem++;
continue;
}
else if(ok(ind,arr[tem].ind))
{
//cout<<ind<<" "<<arr[tem].ind<<"fu \n";
par[arr[tem].ind]=ind;
}
tem++;
}
}
return ;
}
signed main()
{
ios_base::sync_with_stdio(false);
/*cin.tie(0);
cout.tie(0);*/
/* input
11
9 9 2
13 2 1
11 8 2
3 3 2
3 12 1
12 14 1
9 8 5
2 8 2
5 2 1
14 4 2
14 14 1
*/
cin>>N;
for(int A=1;A<=N;A++)
{
cin>>x_>>y_>>r_;
order[A]=A;
lol[A].init(x_,y_,r_,A);
R_cur=max(R_cur,lol[A].R);
}
R_next=R_cur;
init_();
sort(order+1,order+N+1,cmp);
for(int A=1;A<=N;A++)
{
if(par[order[A]])
continue;
solve(order[A]);
}
for(int A=1;A<=N;A++)
cout<<par[A]<<" ";
return 0;
}
Compilation message
circle_selection.cpp:21:36: error: ISO C++ forbids declaration of 'init' with no type [-fpermissive]
init(int X_,int Y_,int R_,int ind_)
^
circle_selection.cpp: In member function 'int circle::init(long long int, long long int, long long int, long long int)':
circle_selection.cpp:27:2: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
