Codeforces Round 158 (Div. 2) |
---|
Закончено |
Государство Флатландия представляет собой бесконечную двумерную плоскость. Во Флатландии есть n городов, каждый из которых является точкой на плоскости.
Правит Флатландией Король Круг IV. У Круга IV есть 9 сыновей. Каждому из своих сыновей Круг хочет отдать во владение часть Флатландии. Для этого он хочет провести четыре различные прямые, так, что две из них параллельны оси Ox, а другие две параллельны оси Oy. При этом ни одна прямая не должна проходить через какой-либо город. Таким образом Флатландия будет разделена на 9 частей, а каждому сыну будет отдана ровно одна из этих частей. Немного подумав и оценив послушность сыновей, Круг IV решил, что i-тому сыну должна достаться часть Флатландии, на которой находится ровно ai городов.
Помогите Кругу найти такие четыре прямые, что если разделить этими прямыми Флатландию на 9 частей, то получившиеся части можно будет раздать сыновьям так, чтобы сыну с номером i досталась часть Флатландии, на которой находится ai городов.
В первой строке находится целое число n (9 ≤ n ≤ 105) — количество городов во Флатландии. В следующих n строках находятся по два целых числа, разделенных пробелом: xi, yi ( - 109 ≤ xi, yi ≤ 109) — координаты i-того города. Никакие два города не находятся в одной точке. В последней строке находится девять чисел, разделенных пробелами: .
Если решения не существует, то выведите единственное целое число -1.
Иначе, в первой строке выведите два различных вещественных числа, разделенных пробелом: x1, x2 — абсциссы прямых, параллельных оси Oy, а во второй строке выведите два различных вещественных числа, разделенных пробелом: y1, y2 — ординаты прямых, параллельных оси Ox. Если решений несколько выведите любое.
При проверке ответа, считается, что город лежит на прямой, если расстояние от города до прямой не превышает 10 - 6. Две прямые считаются одинаковыми, если расстояние между ними не превышает 10 - 6.
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.5000000000 2.5000000000
1.5000000000 2.5000000000
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
-3.5000000000 2.0000000000
3.5000000000 -1.0000000000
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
-1
Решение для первого теста показано ниже:
Решение для второго теста показано ниже:
Для третьего теста решения не существует.
Название |
---|