printРабочее место участника

printЗадачи

1261. Four Points

Ограничения: время – 3s/6s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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.
9090.png
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
The first four lines of the input file contain two integer numbers `x_i` and `y_i` each – coordinates of the `i`-th point (`-1\ 000\ ≤\ x_i,\ y_i\ ≤\ 1\ 000`). No two points coincide, no three points are collinear.
Output
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 Input 1

6 13
11 12
9 2
2 6

Sample Output 1

6 0
15 6
9 15
0 9

Sample Input 2

0 0
5 5
5 0
3 2

Sample Output 2

0 0
0 0
0 0
0 0
Source: ACM ICPC NEERC Northern Subregional 2009
loading