#P18696. Disk Tree
Disk Tree
Disk Tree
题目描述
给定平面上的 个圆盘,它们的半径可以不同。任意两个圆盘既不相交,也不相切。圆盘的边界属于圆盘区域。
你需要画出 条直线段连接这些圆盘,使得从任意一个圆盘出发,都能沿着一条只在圆盘区域内以及这些线段上行走的路径,到达任意另一个圆盘。
画出的线段还必须满足以下限制:
- 所有线段的两个端点都具有整数坐标。
- 每条线段至多与两个圆盘接触或相交。
- 任意两条线段不能相交,也不能接触。唯一的例外是:允许两条线段共用一个端点。
输入格式
第一行包含一个整数 (),表示圆盘的数量。
接下来 行,每行包含三个整数 (,),表示第 个圆盘的圆心为 ,半径为 。
保证任意两个圆盘既不相交,也不相切。
输出格式
如果存在满足要求的方案,输出 YES;否则输出 NO。
如果输出 YES,接下来的 行给出线段。每行包含四个整数 ,表示连接 和 的线段。这两个点必须不同,并且必须满足 。
可以证明,如果存在方案,就一定存在所有线段端点坐标均满足上述范围的方案。输出任意一个合法方案即可。
样例 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 页提取,保留圆盘和四条线段的原始绘制。
