因为圆是从大往小选的，所以每次选出一个圆，它能删掉的圆一定在两倍半径范围之内，假设我们有一个数据结构可以快速把两倍半径范围内的圆找出来，那么直接对这些圆暴力判交就可以了.
我们考虑这个算法中，每个圆会跟多少个比它大的圆暴力判交. 假设这些圆构成集合$S$，那么$S$中的圆两两不交（否则一定有一个会被另一个先删去）. 于是$S$中的圆最多只有常数个，因此这么做的时间复杂度是得到保障的.
现在问题变成如何快速找出两倍半径范围内的圆. 理论上kdtree是可以做的，但我也不知道为什么就T飞了……
事实上，我们不需要真的只找出两倍半径以内的圆，可以划分得更粗略一些. 假设当前选出的圆半径为$r$，我们可以把平面划分成若干个$r\times r$的格子，找出以当前圆为中心的$5\times 5$的网格中的所有圆，时间复杂度的证明同上. 此时，如果$r$是确定的，那么用hashmap套vector就可以维护了. 不过现在$r$是不确定的，如果每次$r$变化都重新划分的话，时间复杂度就会达到$\mathcal O(n^2)$，还不如暴力. 这个时候我们可以划分得再粗略一些，对于半径为$r$的选出的圆，取$k=\max _{2^{k _0}\ge r}k _0$，把平面划分成若干个$2^k\times 2^k$的格子. 这样重新划分的次数为$\mathcal O(\log x)$，时间复杂度的证明仍然类似上面.
最后的时间复杂度为$\mathcal O(n\log x)$.
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
using namespace std;
ele n,w,mx,x[maxn],y[maxn],r[maxn],a[maxn],res[maxn];
unordered_map<ele,vector<pair<ele,ele> > > mp;
inline bool cmp1(ele i,ele j){
return (r[i]==r[j])?i<j:r[i]>r[j];
}
inline void clear(){
for (auto it=mp.begin(); it!=mp.end(); ++it)
it->se.clear();
mp.clear();
}
inline void build(){
for (int i=0; i<n; ++i)
mp[x[i]>>w].push_back(make_pair(y[i],i));
for (auto it=mp.begin(); it!=mp.end(); ++it)
sort(it->se.begin(),it->se.end());
}
inline ele _sqr(ele x){
return x*x;
}
inline void test(ele i,ele j){
if (~res[j]) return;
if (_sqr(x[i]-x[j])+_sqr(y[i]-y[j])<=_sqr(r[i]+r[j])) res[j]=i;
}
int main(){
scanf("%lld",&n);
mx=0;
for (int i=0; i<n; ++i) scanf("%lld%lld%lld",x+i,y+i,r+i),mx=max(mx,r[i]);
w=1;
while ((1<<w)<mx) ++w;
build();
memset(res,-1,sizeof(res));
for (int i=0; i<n; ++i) a[i]=i;
sort(a,a+n,cmp1);
for (int j=0; j<n; ++j){
if (~res[a[j]]) continue;
ele i=a[j];
if (w && ((1<<w-1)>=r[i])){
while ((1<<w-1)>=r[i]) --w;
clear();
build();
}
for (int k=(x[i]>>w)-2; k<=(x[i]>>w)+2; ++k){
if (mp.find(k)==mp.end()) continue;
ele u=lower_bound(mp[k].begin(),mp[k].end(),make_pair(y[i]-r[i]*2,0ll))
-mp[k].begin();
ele v=upper_bound(mp[k].begin(),mp[k].end(),make_pair(y[i]+r[i]*2,n))
-mp[k].begin();
for (int p=u; p<v; ++p) test(i,mp[k][p].se);
}
}
for (int i=0; i<n; ++i) printf(i?" %lld":"%lld",res[i]+1);
puts("");
return 0;
}