「BZOJ5465」[APIO2018] 选圆圈

Description

在平面上,有 nn 个圆,记为 c1,c2,,cnc_1, c_2, \ldots, c_n 。我们尝试对这些圆运行这个算法:

  1. 找到这些圆中半径最大的。如果有多个半径最大的圆,选择编号最小的。记为 cic_i
  2. 删除 cic_i 及与其有交集的所有圆。两个圆有交集当且仅当平面上存在一个点,这个点同时在这两个圆的圆周上或圆内。(原文直译:如果平面上存在一个点被这两个圆所包含,我们称这两个圆有交集。一个点被一个圆包含,当且仅当它位于圆内或圆周上。)
  3. 重复上面两个步骤直到所有的圆都被删除。

cic_i 被删除时,若循环中第一步选择的圆是 cjc_j ,我们说 cic_icjc_j 删除。对于每个圆,求出它是被哪一个圆删除的。

Input

第一行包含一个整数 nn ,表示开始时平面上圆的数量 (1n31051 \le n \le 3 \cdot 10^5)。

接下来 nn 行,每行包含三个整数 xi,yi,rix_i, y_i, r_i 依次描述圆 cic_i 圆心的 xx 坐标、yy 坐标和它的半径 (109xi,yi109-10^9 \le x_i, y_i\le 10^9, 1ri1091\le r_i\le 10^9)。
Output
输出一行,包含 nn 个整数 a1,a2,...ana_1, a_2, ... a_n ,其中 aia_i 表示圆 cic_i 是被圆 caic_{a_i} 删除的。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
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

Sample Output

1
7 2 7 4 5 6 7 7 4 7 6

题目描述中的图片对应了样例中的情形。

Hint

子任务 1(7 分):n5000n \le 5000

子任务 2(12 分):n3105n \le 3 \cdot 10^5, 对于所有的圆 yi=0y_i=0

子任务 3(15 分):n3105n \le 3 \cdot 10^5, 每个圆最多和一个其他圆有交集。

子任务 4(23 分):n3105n \le 3 \cdot 10^5, 所有的圆半径相同。

子任务 5(30 分):n105n \le 10^5

子任务 6(13 分):n3105n \le 3 \cdot 10^5

Solution

Kdtree裸体。

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 3e5 + 6;
int n, siz[N];
const int inf = 1e9 + 7;
int ans[N];
struct Cir {
ll x, y, r;
int i;
}a[N],b[N];
bool cmpr(Cir _x, Cir _y) {
if(_x.r == _y.r) return _x.i < _y.i;
return _x.r > _y.r;
}
bool cmpx(Cir _x, Cir _y) {
return _x.x < _y.x;
}
bool cmpy(Cir _x, Cir _y) {
return _x.y < _y.y;
}
struct Tree {
Cir c;
ll x1, y1, x2, y2;
int l, r;
}t[N];
void up(int o) {
t[o].x1 = min(t[o].c.x - t[o].c.r, min(t[t[o].l].x1, t[t[o].r].x1));
t[o].x2 = max(t[o].c.x + t[o].c.r, max(t[t[o].l].x2, t[t[o].r].x2));
t[o].y1 = min(t[o].c.y - t[o].c.r, min(t[t[o].l].y1, t[t[o].r].y1));
t[o].y2 = max(t[o].c.y + t[o].c.r, max(t[t[o].l].y2, t[t[o].r].y2));
siz[o] = siz[t[o].l] + siz[t[o].r] +(ans[t[o].c.i] == 0);
}
int rt,tot;
void build(int &o, int l, int r, bool c) {
o = ++tot;
int mid = (l + r) >> 1;
if(!c) nth_element(a + l, a + mid, a +r + 1, cmpx);
else nth_element(a + l, a + mid, a + r + 1, cmpy);
t[o].c = a[mid];
if(l < mid) build(t[o].l, l, mid - 1, c ^ 1);
if(r > mid) build(t[o].r, mid + 1, r, c ^ 1);
up(o);
}
bool in(Cir x, Cir &y) {
ll d1 = sqr(x.x - y.x) + sqr(x.y - y.y);
return d1 <= sqr(x.r + y.r);
}
bool check(int x, Cir &y) {
ll res = 0;
if(y.x < t[x].x1) res = sqr(t[x].x1 - y.x);
if(y.x > t[x].x2) res = sqr(t[x].x2 - y.x);
if(y.y < t[x].y1) res += sqr(t[x].y1 - y.y);
if(y.y > t[x].y2) res += sqr(t[x].y2 - y.y);
return res <= sqr(y.r);
}
void query(int o, Cir &x) {
if(!ans[t[o].c.i] && in(t[o].c, x))
ans[t[o].c.i] = x.i;
// printf("cir=%d (%lld,%lld),(%lld,%lld) l=%d,r=%d\n", t[o].c.i, t[o].x1,t[o].y1,t[o].x2,t[o].y2,t[t[o].l].c.i,t[t[o].r].c.i);
if(t[o].l && siz[t[o].l] && check(t[o].l, x))
query(t[o].l, x);
if(t[o].r && siz[t[o].r] && check(t[o].r, x))
query(t[o].r, x);
up(o);
}
int main() {
n = read();
t[0].x1 = t[0].y1 = inf;
t[0].x2 = t[0].y2 = -inf;
for(int i = 1; i <= n; ++i) {
a[i].x = read(), a[i].y = read();
a[i].r = read();
a[i].i = i;
b[i] = a[i];
}
sort(b + 1, b +1 + n, cmpr);
build(rt, 1, n, 0);
for(int i = 1; i <= n; ++i)
if(!ans[b[i].i])
query(rt, b[i]);
for(int i = 1; i <= n; ++i)
printf("%d ", ans[i]);
puts("");
return 0;
}