Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

E. Горох-Сити
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Царь Горох был мудрым и дальновидным правителем. Всё время проводил в государственных делах и заботах. Государство развивалось, народ размножался и строился. Новые дома росли, как грибы после дождя. Соседние цари завидовали и подумывали о войне. Чтобы обезопасить столицу от врагов, задумал царь Горох построить новую каменную стену, охватывающую всю столицу с её домами.

Для того, чтобы карта города красиво смотрелась на стене в кабинете царя, было принято решение о том, что столица должна иметь прямоугольные границы. При этом площадь города должна оставаться минимально возможной, а все N домов, зарегистрированные в муниципалитете, должны оказаться в границах прямоугольного города.

Входные данные

В первой строке входного файла целое число N — количество домов в городе (3 ≤ N ≤ 80 000). В следующих N строках пары целых чисел X, Y — декартовы координаты домов ( - 25 000 ≤ X, Y ≤ 25 000). Гарантируется, что в городе есть как минимум три дома, не лежащие на одной прямой.

Выходные данные

В четырех строках выведите координаты вершин прямоугольника в порядке обхода против часовой стрелки. Координаты следует выводить с точностью не менее 5 знаков после запятой. Ответ считается верным, если абсолютная или относительная погрешность значения площади прямоугольника не превосходит 10 - 5 и все дома лежат внутри него или находятся на расстоянии менее 10 - 5 от его сторон.

Примеры
Входные данные
3
0 0
2 2
2 0
Выходные данные
0.0000000000 0.0000000000
1.0000000000 -1.0000000000
3.0000000000 1.0000000000
2.0000000000 2.0000000000