Public Judge

pjudge

Time Limit: 1 s Memory Limit: 1024 MB Total points: 100

#21692. 【NOIP Round #3】移除石子

Statistics

题目描述

你正在玩一个名为“移除石子”的小游戏。

平面直角坐标系上有 $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.hchecker.cpp,将其置于同一目录下编译,然后运行 checker input output output 即可,这里 input output 分别是输入文件和你的输出。

如果你不熟悉命令行

没关系!你只需要严格按照下面的步骤执行就可以了。

  1. 先把你要测试的输入数据改名为 stone.in,你的输出文件改名为 stone.out
  2. 把第一步里的两个文件复制到同一个文件夹(把这个文件夹叫做工作文件夹)里。
  3. 下发文件里有四个文件 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 就可以了。
  4. 上面你删掉了一个文件,还会剩下三个文件。你需要把剩下的三个文件复制到工作文件夹里。
  5. 在工作文件夹里,编译 checker.cpp,如果你使用 Dev-C++,那快捷键是 F9。如果无误,应该会看到在工作文件夹下里生成了文件 checker.exe
  6. 在工作文件夹里,编译并运行 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+81e8 等科学计数法形式的实数是不合法的。

样例 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}$