#2586. 「APIO2018」选圆圈

内存限制:1024 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: zjq

题目描述

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

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

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

输入格式

第一行包含一个整数 nnn ,表示开始时平面上圆的数量 (1≤n≤3⋅1051 \le n \le 3 \cdot 10^51n3105)。

接下来 nnn 行,每行包含三个整数 xi,yi,rix_i, y_i, r_ixi,yi,ri 依次描述圆 cic_ici 圆心的x坐标、y坐标和它的半径 (−109≤xi,yi≤109-10^9 \le x_i, y_i\le 10^9109xi,yi109, 1≤ri≤1091\le r_i\le 10^91ri109)。

输出格式

输出一行,包含 nnn 个整数 a1,a2,...ana_1, a_2, ... a_na1,a2,...an ,其中 aia_iai 表示圆 cic_ici 是被圆 caic_{a_i}cai 删除的。

样例

样例输入

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

样例输出

7 2 7 4 5 6 7 7 4 7 6

样例解释

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

数据范围与提示

子任务 1(7 分):n≤5000n \le 5000n5000

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

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

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

子任务 5(30 分):n≤105n \le 10^5n105

子任务 6(13 分):n≤3⋅105n \le 3 \cdot 10^5n3105