Baltic Olympiad in Informatics: 2014 Day 2, Problem 1

For a long time the island of Bytopia was ruled by the fair king Byteasar. But after the sudden death of the king, his two sons—twins Biteon and Byteon—could not come to an agreement which one of them should ascend the throne. Therefore they decided to divide the island into two provinces to rule them independently.

On a rectangular map Byteotia is shaped as a polygon of $N$ vertices. Every side of the polygon is parallel to a side of the map, and every two consecutive sides are perpendicular to each other. No side of the polygon crosses or touches any other side, except for the common endpoints of consecutive sides.

Biteon and Byteon want to divide the polygon into two congruent polygons, using one line segment contained in the polygon and parallel to a side of the map. (Two polygons are congruent if one can be transformed into the other using a combination of reflections, rotations and translations.) Coordinates of the polygon vertices and the endpoints of the dividing segment are integers. The king's sons asked you to verify whether such a division is possible.

Given the shape of the island, determine if it can be partitioned by a horizontal or vertical segment into two congruent pieces. If it can, find one such segment.

Constraints

Subtask 1 [12%]

$4\le N\le {10}^5$

Any horizontal or vertical line that divides the polygon divides it into exactly two parts.

Subtask 2 [15%]

$4\le N\le 200$

Subtask 3 [23%]

$4\le N\le 2000$

Subtask 4 [50%]

$4\le N\le {10}^5$

Input Specification

The first line of the input contains a single integer $N$, the number of vertices. The $i^{\text{th}}$ of the next $N$ lines contains two-space separated integers $X_i$ and $Y_i$ $(0\le X_i,Y_i\le {10}^9)$, which are the coordinates of the $i^{\text{th}}$ vertex.

The vertices are given in order, i.e. the line segments $(X_1,Y_1)-(X_2,Y_2),(X_2,Y_2)-(X_3,Y_3),\dots ,(X_{N-1},Y_{N-1})-(X_N,Y_N)$ and $(X_N,Y_N)-(X_1,Y_1)$ are all sides of the polygon. Furthermore, any two consecutive line segments are perpendicular to each other.

Output Specification

Your program should output a single line. If it is possible to divide the island into congruent parts with a horizontal or vertical segment with endpoints $(x_1,y_1)$ and $(x_2,y_2)$, print $4$ integers $x_1,y_1,x_2$ and $y_2$, separated by spaces. Either $x_1=x_2$ or $y_1=y_2$ must hold. The segment should be contained within the polygon and only its endpoints should touch the boundary.

If a suitable division cannot be found, output a single word NO.

Sample Input 1

10
0 0
1 0
1 1
3 1
3 5
2 5
2 3
1 3
1 2
0 2

Sample Output 1

1 2 3 2

Explanation for Sample 1

Note that $3212$ is also a valid solution.

Sample Input 2

6
0 0
1 0
1 1
2 1
2 2
0 2

Sample Output 2

NO

Explanation for Sample 2

In this case there is no way to divide the island into two congruent parts.