402047: GYM100633 E Pea-City

The Pea King was a wise ruler and a good strategist. He spent all his time dealing with the state affairs. As the kingdom grew, population increased. The new houses popped up everywhere like mushrooms after the rain. The kings of neighboring states were becoming envious and started to plan a war. In order to protect the capital from the invaders, the Pea King decided to build a new city wall around the capital borders that would lock all the buildings on the city outskirts inside of it as well.

For the aesthetic effect, namely to make the map on the wall in king’s parlor look pretty, it was decided that the capital city should have rectangular borders. Keeping this in mind the total land area should remain as minimal as possible and all the N houses registered should stay inside the borders of the rectangular city.

The first line contains single integer N — number of houses in the city (3 ≤ N ≤ 80 000). The following N lines contain pairs of integers X, Y — Cartesian coordinates of the houses ( - 25 000 ≤ X, Y ≤ 25 000). It’s guaranteed that there are at least three houses not on one line.

Output the coordinates of the rectangular corner points in the counterclockwise order, each pair of coordinates on a separate line. The answer is considered correct if the absolute or relative error for rectangular area does not exceed 10^- 5 and all houses are strictly inside the city or at the distance not exceeding 10^- 5 from its borders.

3
0 0
2 2
2 0

0.0000000000 0.0000000000
1.0000000000 -1.0000000000
3.0000000000 1.0000000000
2.0000000000 2.0000000000