Building a Fence

Several apple trees stand in a field. Build a rectangular fence with the smallest possible area that contains every apple tree.

Each tree position is given as an integer coordinate on the plane. All four vertices of the fence must also have integer coordinates. The sides of the rectangle do not have to be parallel to the coordinate axes.

If more than one fence is possible, choose one using the output rule.

The first line contains the number of apple trees, n.

Each of the next n lines contains two integers x and y, the coordinates of one apple tree.

n is between 1 and 1,000, inclusive. Every x and y is between -20,000 and 20,000, inclusive.

Print the four vertices of a minimum-area rectangular fence, one vertex per line. Each line must contain the x and y coordinates of that vertex separated by a space.

The vertices must be listed in clockwise order. If several minimum-area fences exist, consider every clockwise listing that can be formed by choosing any starting vertex, and print the lexicographically smallest listing. Compare a vertex by (x, y), and compare four-line listings from the first line onward.

If the minimum area is 0, let p and q be the two farthest endpoints, chosen so that p is lexicographically smaller. Print p, q, q, p in that order.