题目描述
你正在玩一个名为“移除石子”的小游戏。
平面直角坐标系上有 $n$ 颗石子,放置在整点(横纵坐标均为整数的点)上,第 $i$ 颗石子的坐标为 $(x_i,y_i)$。保证 $n$ 颗石子的坐标互不相同。保证 $n$ 为偶数。
你需要操控一个机器人移除所有的石子。你要做恰好 $n/2$ 次操作,每次操作中:
- 首先,你在平面上画出一个正方形。正方形的边必须与坐标轴平行。正方形的顶点可以不是整点。
- 机器人会移走所有在正方形内部(包括边界上)的石子。
因为机器人有两只机械臂,你也不想让机器人太闲或者太累,所以要求每次你画出的正方形里恰好有两颗石子。这也意味着,做完所有操作后,所有石子全部被移除了。
石子被移走后就不在这个平面上了,不会对后续操作造成影响,你可以认为它们被丢进了垃圾桶里。
你想知道,是否存在一种合法方案?如果存在的话,请你输出任意一组合法方案。
输入格式
本题单个测试点内有多组数据。
第一行一个正整数 $T$ 表示数据组数。
对于每组数据:第一行为一个正整数 $n$,表示石子的个数。
接下来 $n$ 行,每行两个整数 $x_i,y_i$,描述一颗石子的坐标。
输出格式
对于每组数据:
如果不存在方案,输出 No
。
否则,第一行输出 Yes
。
接下来输出 $n/2$ 行,第 $i$ 行四个实数 $x_1,y_1,x_2,y_2$。$(x_1,y_1),(x_2,y_2)$ 是第 $i$ 次操作时,你画出的正方形的任意两个相对的顶点。你需要按照操作的时间顺序输出。
输出的实数应当:
- 用十进制形式输出,不能用科学计数法。
- 至多保留四位小数。
如果有多种方案你可以输出任意一种。No
Yes
对大小写不敏感,也就是 YES
nO
也算对。
如何知道你的输出是否正确
如果你熟悉命令行 / 终端操作
下发文件中有两个文件 testlib.h
和 checker.cpp
,将其置于同一目录下编译,然后运行 checker input output output
即可,这里 input
output
分别是输入文件和你的输出。
如果你不熟悉命令行
没关系!你只需要严格按照下面的步骤执行就可以了。
- 先把你要测试的输入数据改名为
stone.in
,你的输出文件改名为stone.out
。 - 把第一步里的两个文件复制到同一个文件夹(把这个文件夹叫做工作文件夹)里。
- 下发文件里有四个文件
testlib.h,checker.cpp,run_windows.cpp,run_linux.cpp
。如果你用的是 Windows 系统,请你删掉run_linux.cpp
;Linux 则删掉run_windows.cpp
。下面我们都假设你用的是 Windows 系统,如果不是的话,只需要把涉及到run_windows.cpp
的步骤全部改为run_linux.cpp
就可以了。 - 上面你删掉了一个文件,还会剩下三个文件。你需要把剩下的三个文件复制到工作文件夹里。
- 在工作文件夹里,编译
checker.cpp
,如果你使用 Dev-C++,那快捷键是 F9。如果无误,应该会看到在工作文件夹下里生成了文件checker.exe
。 - 在工作文件夹里,编译并运行
run_windows.cpp
,如果你使用 Dev-C++,那快捷键是 F11。如果这个程序运行之后显示“OK”,则你的输出是正确的。否则你的输出不正确。注意,这一步的程序运行时间可能比较长,请耐心等待。
样例输入输出
样例输入 1
1
4
1 1
2 2
5 5
6 6
样例输出 1
Yes
2 2 5 5.0000
1 1 6 6.000
样例 1 解释
第一次,我们移走了第二颗石子和第三颗石子。第二次,我们移走了第一颗石子和第四颗石子。
输出不唯一,比如下面的输出也合法:
yEs
0.9999 0.9999 2.0001 2.0001
-233 -1.0 233.000 465.00
在上面的输出中,第一次,我们移走了第一颗石子和第二颗石子。第二次,我们移走了第三颗石子和第四颗石子。
但是下面的输出不合法:
Yes
1 1 2 2
-1e+5 -1e+5 1e+6 1e+6
因为不能用科学计数法输出。
下面的输出也不合法:
Yes
1 1 5 5
2 2 6 6
因为第一次删的时候,正方形内部和边界上一共有 $3$ 个点 $(1,1),(2,2),(5,5)$。
下面的输出也不合法:
Yes
1 1 1 2
5 5 6 6
因为 $(1,1)$ 和 $(1,2)$ 不可能是任何边平行于坐标轴的正方形的对角。
下面的输出也不合法:
Yes
1 1 2 2
5 5 6 6.00000
因为至多只能输出 4 位小数。
样例输入 2
1
4
0 0
100000000 200000000
200000000 100000000
400000000 400000000
样例输出 2
Yes
100000000 100000000 200000000 200000000
-0.1 -0.100 400000000.0 400000000.0
样例 2 解释
注意输出 1e+8
或 1e8
等科学计数法形式的实数是不合法的。
样例 3/4
见下发文件。
样例 3 满足测试点 $5$ 的性质。
样例 4 满足测试点 $8,9$ 的性质。
数据范围
本题 $10$ 个测试点,每个测试点 $10$ 分。对于所有测试点,保证 $1\le T\le 60,2\le n\le 3000,0\le x_i,y_i\le 10^9$。保证 $n$ 是偶数,保证石子的坐标互不相同。
表中“数据随机”的意思是石子的横纵坐标均在 $[0,10^9]$ 随机生成。
测试点编号 | $T\le $ | $n\le $ | 特殊性质 |
---|---|---|---|
$1,2$ | $1$ | $6$ | $x_i=2i,y_i=2i$ |
$3$ | $3000$ | ||
$4$ | $6$ | $x_i=0$ | |
$5$ | $3000$ | ||
$6,7$ | $10$ | 数据随机 | |
$8,9$ | $20$ | $500$ | |
$10$ | $60$ | $3000$ | 无 |
时间限制:$1\texttt{s}$
空间限制:$1024\texttt{MB}$