Problem F. Four Points

Author:ACM ICPC 2009-2010, NEERC, Northern Subregional Contest   Time limit:3 sec
Input file:four.in   Memory limit:256 Mb
Output file:four.out  

Statement

Mike is a magician. One of his inventions is a labyrinth that gives supernatural abilities to every person who walks through it. The labyrinth has an extremely complicated internal structure, however, for an external observer it is just a square on the ground.

Mike has found some suitable place for labyrinth on the seashore. He drew its border on the sand and marked four points with small stones so that each side of the square contained exactly one stone and no stone was placed in the corner.

As no picture drawn on the sand stays forever, after a while Mike found only the stones on their places. Now he wonders where the marked square could have been.

Your task is to restore some possible place of the labyrinth and return four corners of the square as a result. You may assume that the seashore is a plane and the stones are points on it.

Input file format

The first four lines of the input file contain two integer numbers xi and yi each — coordinates of the i-th point ( − 1 000 ≤ xi, yi ≤ 1 000). No two points coincide, no three points are collinear.

Output file format

Output four lines containing two real numbers each — coordinates of the vertices of the square. Vertices should be listed in either clockwise or counterclockwise order. Coordinates must be precise up to 6 digits after the decimal point.

If there are multiple solutions, output any of them. If there is no solution, write four pairs of zeroes instead of the coordinates.

Sample tests

No. Input file (four.in) Output file (four.out)
1
6 13
11 12
9 2
2 6
6 0
15 6
9 15
0 9
2
0 0
5 5
5 0
3 2
0 0
0 0
0 0
0 0

0.065s 0.010s 15