QOJ.ac

QOJ

実行時間制限: 10 s メモリ制限: 1024 MB 満点: 39

#5929. X Marks the Spot

統計

公平的泰隆国王和他的四个儿子征服了卡拉尼亚国。他的四个儿子立刻开始争吵,想要瓜分这片土地。争论的焦点是卡拉尼亚的金矿——每个儿子都希望自己分到的金矿数量不少于其他任何一个兄弟。

泰隆国王很快就厌倦了这种争吵,尤其是当他得知金矿的总数是 $4N$ 时,他认为分配应该很容易。他召集了儿子们,拿出一张地图,在上面画了一个“X”,并宣布每个儿子将获得该国四分之一的土地,边界由他画的“X”定义。

不幸的是,泰隆国王有点近视,他画图用的地图并不是卡拉尼亚的地图。他的首席大臣迅速藏起了那张地图,现在试图在卡拉尼亚的地图上画一个一模一样的“X”,使得每个儿子都能得到相同数量的金矿。不幸的是,所有的儿子都看见了国王画“X”的过程,并且知道边界应该是两条互相垂直的直线,所以大臣必须这样画。

帮帮他!你的任务是画出两条互相垂直的直线,使得没有任何金矿位于边界上,并且这些边界将金矿平分。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例以一个数字 $N$ 开头,描述每个儿子应该得到的金矿数量。随后有 $4N$ 行,每行包含两个整数,表示其中一个金矿的坐标 $x_i, y_i$。没有三个金矿是共线的。

输出格式

对于每个测试用例,输出一行 "Case #x: $x_a$ $y_a$ $x_b$ $y_b$",其中 $x$ 是测试用例编号(从 1 开始),$(x_a, y_a)$ 是两条边界交点的坐标,$(x_b, y_b)$ 是“X”上另一个点的坐标。

所有坐标必须在 $-10^9$ 和 $10^9$ 之间,小数点后最多有 9 位数字,且不能使用科学计数法。它们必须是精确的:最终的“X”将完全按照这些坐标绘制。如果不存在合适的边界放置方案,你应该输出 IMPOSSIBLE。

数据范围

$1 \le T \le 20$ $-10^6 \le x_i, y_i \le 10^6$ $1 \le N \le 2500$

样例

样例输入 1

2
1
0 0
1 0
0 1
1 1
1
1 0
0 1
-1 0
0 -1

样例输出 1

Case #1: 0.5 0.5 2 0.5
Case #2: 0 0 -3 -3

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.