← 返回题目列表

Codeforces · 260/E

E. 分裂王国

中文机器翻译题面 查看原题

一个叫做Flatland的国家是一个无限的二维平面。 Flatland 有 n 个城市,每个城市都是平面上的一个点。

平地由国王 Circle IV 统治。圆四有9个儿子。他想给他的每个儿子统治平地的一部分。为此,他想要绘制四条不同的直线,其中两条平行于 Ox 轴,另外两条平行于 Oy 轴。那时,没有一条直线可以穿过任何城市。因此,Flatland 将被分为 9 个部分,每个儿子将被分配到这些部分中的一个。圆四想了想,评估了儿子们的服从程度,决定让第 i 个儿子得到平地正好有 a 个城市的那部分。

帮助Circle找到这样4条直线,如果我们用这些线将Flatland分成9部分,得到的部分可以给儿子们,这样子号i就得到了包含ai城市的Flatland部分。

输入

第一行包含整数 n (9 ≤ n ≤ 105) — Flatland 中的城市数量。接下来的 n 行每行包含两个以空格分隔的整数: xi, yi (- 109 ≤ xi, yi ≤ 109) — 第 i 个城市的坐标。没有两个城市位于同一点。最后一行包含九个空格分隔的整数:$$a_{1},a_{2},\cdots,a_{9}\ (1\leq a_{i}\leq 10^{5}),\sum_{i=1}^{9}a_{i}=n$$。

输出

如果没有解,则打印单个整数-1。

否则,在第一行打印两个不同的实数空格分隔的数字:x1、x2 — 平行于 Oy 轴的直线的横坐标。在第二行中打印两个不同的实数,以空格分隔:y1,y2 - 与 Ox 平行的直线的纵坐标。如果有多个解决方案,请打印其中任何一个。

检查答案时,如果城市与直线之间的距离不超过 10 - 6,则认为城市位于直线上。如果两条直线之间的距离不超过 10 - 6,则认为两条直线相同。

示例

输入 #1

9
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
1 1 1 1 1 1 1 1 1

输出 #1

1.5000000000 2.5000000000
1.5000000000 2.5000000000

输入 #2

15
4 4
-1 -3
1 5
3 -4
-4 4
-1 1
3 -3
-4 -5
-3 3
3 2
4 1
-4 2
-2 -5
-3 4
-1 4
2 1 2 1 2 1 3 2 1

输出 #2

-3.5000000000 2.0000000000
3.5000000000 -1.0000000000

输入 #3

10
-2 10
6 0
-16 -6
-4 13
-4 -2
-17 -10
9 15
18 16
-5 2
10 -5
2 1 1 1 1 1 1 1 1

输出 #3

-1

注意

第一个样例测试的解决方案如下所示:

第二个样例测试的解决方案如下所示:

第三个样本测试没有解决方案。