#P8651. nonintersect
nonintersect
计算几何
题目描述
给定平面上 个点,以及把这些点两两配对得到的 条线段。设这些原线段的长度总和为 。
重新把这 个点两两配对,连成 条线段。每个点恰好作为一条线段的端点,任意两条新线段不能相交(也不能接触或重叠)。设新线段的长度总和为 。
请构造满足 的方案。如果不存在这样的方案,输出 ORZ。满足条件的任意方案均可。
输入格式
第一行一个整数 。
接下来 行,每行两个整数 ,表示第 个点的坐标。
接下来 行,每行两个整数 ,表示一条原线段连接第 个点。保证每个点恰好在一条原线段中出现。
输出格式
有解时输出 行,每行两个不同的点编号,表示一条新线段。
无解时仅输出一行 ORZ。
样例
2
1 1
1 4
5 1
5 4
1 4
2 3
1 3
2 4
数据范围与约定
全部数据满足 ,,所有点互不相同。
子任务 1 允许共线,且所有点的 。其他子任务保证任意三个点不共线。
| 子任务 | 分值 | 附加限制 |
|---|---|---|
| 1 | 3 | 所有 |
| 2 | 4 | |
| 3 | 8 | |
| 4 | 25 | |
| 5 | 4 | |
| 6 | 10 | |
| 7 | 36 | |
| 8 | 10 |
本题采用构造检查器验证方案,不要求与参考输出相同。