Baltic OI '14 P4 - Demarcation

View as PDF

Submit solution


Points: 40 (partial)
Time limit: 0.5s
Memory limit: 256M

Problem types
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 2\,000

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 3\ 2\ 1\ 2 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.


Comments

There are no comments at the moment.