#P18696. Disk Tree

Disk Tree

Disk Tree

题目描述

给定平面上的 nn 个圆盘,它们的半径可以不同。任意两个圆盘既不相交,也不相切。圆盘的边界属于圆盘区域。

你需要画出 n−1n-1 条直线段连接这些圆盘,使得从任意一个圆盘出发,都能沿着一条只在圆盘区域内以及这些线段上行走的路径,到达任意另一个圆盘。

画出的线段还必须满足以下限制:

  • 所有线段的两个端点都具有整数坐标。
  • 每条线段至多与两个圆盘接触或相交。
  • 任意两条线段不能相交,也不能接触。唯一的例外是:允许两条线段共用一个端点。

输入格式

第一行包含一个整数 nn(2≤n≤200 0002\le n\le 200\,000),表示圆盘的数量。

接下来 nn 行,每行包含三个整数 xi,yi,rix_i,y_i,r_i(0≤xi,yi≤1090\le x_i,y_i\le 10^9,1≤ri≤1091\le r_i\le 10^9),表示第 ii 个圆盘的圆心为 (xi,yi)(x_i,y_i),半径为 rir_i。

保证任意两个圆盘既不相交,也不相切。

输出格式

如果存在满足要求的方案,输出 YES;否则输出 NO。

如果输出 YES,接下来的 n−1n-1 行给出线段。每行包含四个整数 x1,y1,x2,y2x_1,y_1,x_2,y_2,表示连接 (x1,y1)(x_1,y_1) 和 (x2,y2)(x_2,y_2) 的线段。这两个点必须不同,并且必须满足 0≤x1,y1,x2,y2≤1090\le x_1,y_1,x_2,y_2\le 10^9。

可以证明,如果存在方案,就一定存在所有线段端点坐标均满足上述范围的方案。输出任意一个合法方案即可。

样例 1

样例输入

3
1 0 3
10 10 6
0 5 1

样例输出

YES
0 4 7 12
0 0 16 8

样例 2

样例输入

2
1 1 1
3 3 1

样例输出

YES
2 1 3 2

样例 3

样例输入

5
10 10 10
2 0 1
20 20 1
3 20 1
20 0 1

样例输出

YES
1 0 10 10
20 0 10 10
20 10 20 22
3 20 10 10

样例说明

下面是原题对样例 3 的示意图,直接从官方 PDF 第 15 页提取,保留圆盘和四条线段的原始绘制。

样例 3 的官方原图