PEG Judge - WC98

Woburn Challenge 1998

Episode 5: Y2K?? Why, too bad.

The Rebel Alliance is in a crisis. The defence systems at their shipyards on Mos Eisely are going to crash because of the Y2K problem (what else did they expect when they gave Luke the programming assignment on that one). The Empire will be sending in their ATACs soon to destroy the site. Time is of the essence but the Rebels do not have enough time to move all the ships to a safer site. Instead, Obi-Wan Kenobi has assembled some of his best Jedi Knights (Luke, of course, not being one of them) to create a ground-level Force field around their assets. This force field will protect them against the attacks of the Empire until reinforcements arrive. The force field extends in a straight line between Knights, thus eventually forming a closed polygon. However, the power of the Force diminshes over distance and so the Knights wish to create the enclosure of smallest possible area such that all assets are either within OR on the boundary of the forcefield (ie. anything within or on the boundary of the polygon is protected). There is an added complication: the force field enclosure must be convex because concave regions are weak and are easy to penetrate (compare, for example, trying to break an egg shell from the outside versus the inside)

Given a set of points representing ships on the ground, output the locations where the Knights must stand in order to construct the required forcefield. Note that a Knight can be inside a ship (ie. in the same position as the ship, thus protecting the ship). If there are multiple ways to do this, output the one with the smallest possible number of Knights.

Input

Line 1: n (# of ships, n ≤ 5000)
The next n lines represent the coordinates of the ships relative to the center of the shipyard complex. The format is: x y (ie. x and y coordinates separated by 1 space).
All coordinates are integers with each number in the range -16000 ≤ number ≤ 16000.
Each ship is on a separate line.

Output

One on each line, output the coordinates at which the Jedi Knights must stand in order to construct the required forcefield. The points must be in clockwise order (on a standard xy plane) around the forcefield. Do not repeat the first point.