QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 512 MB Total points: 100

#692. 删除点

Statistics

平面上有 $n$ 个点。点的坐标均为整数。$n$ 始终为偶数。

你可以画一个边平行于坐标轴的正方形。其顶点坐标可以是实数。如果正方形内部或边界上恰好有两个点,则这两个点会被删除。

你需要找到一种删除所有点的方法,或者指出这是不可能的。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 3000$),表示点的数量。

接下来的 $n$ 行,每行包含两个整数 $x_i$ 和 $y_i$ ($0 \le x_i, y_i \le 10^9$),描述第 $i$ 个点的坐标。

所有点互不相同。

输出格式

如果无法删除所有点,请在第一行输出 “No”。

否则,在第一行输出 “Yes”。在接下来的 $n/2$ 行中,每行输出四个实数:正方形对角的坐标。正方形应按绘制顺序输出。如果存在多种可能的答案,输出其中任意一种即可。

实数输出时小数点后最多保留四位。输出格式如下:可选的负号,后跟任意位数的整数部分,然后是可选的小数点,最后是最多四位的小数部分。

样例

样例输入 1

4
1 1
2 2
5 5
6 6

样例输出 1

Yes
1.0 1.0 2.0 2.0
5.0 5.0 6.0 6.0

样例输入 2

4
0 0
1 2
2 1
4 4

样例输出 2

Yes
1.0 1.0 2.0 2.0
0.0 0.0 4.0 4.0

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.