#P8651. nonintersect

    ID: 8738 传统题 1000ms 256MiB 尝试: 3 已通过: 2 难度: 8 上传者: 标签>计算几何扫描线数据结构CF2400构造分治排序数学

nonintersect

计算几何

题目描述

给定平面上 2N2N 个点,以及把这些点两两配对得到的 NN 条线段。设这些原线段的长度总和为 XX。

重新把这 2N2N 个点两两配对,连成 NN 条线段。每个点恰好作为一条线段的端点,任意两条新线段不能相交(也不能接触或重叠)。设新线段的长度总和为 YY。

请构造满足 Y≥2πXY\ge\dfrac{2}{\pi}X 的方案。如果不存在这样的方案,输出 ORZ。满足条件的任意方案均可。

输入格式

第一行一个整数 NN。

接下来 2N2N 行,每行两个整数 xi,yix_i,y_i,表示第 ii 个点的坐标。

接下来 NN 行,每行两个整数 a,ba,b,表示一条原线段连接第 a,ba,b 个点。保证每个点恰好在一条原线段中出现。

输出格式

有解时输出 NN 行,每行两个不同的点编号,表示一条新线段。

无解时仅输出一行 ORZ。

样例

2
1 1
1 4
5 1
5 4
1 4
2 3
1 3
2 4

数据范围与约定

全部数据满足 1≤N≤50001\le N\le5000,1≤xi,yi≤1000001\le x_i,y_i\le100000,所有点互不相同。

子任务 1 允许共线,且所有点的 yi=1y_i=1。其他子任务保证任意三个点不共线。

子任务 分值 附加限制
1 3 所有 yi=1y_i=1
2 4 N≤5N\le5
3 8 N≤8N\le8
4 25 N≤50N\le50
5 4 N≤100N\le100
6 10 N≤500N\le500
7 36 N≤1000N\le1000
8 10 N≤5000N\le5000

本题采用构造检查器验证方案,不要求与参考输出相同。