Description

Given a polygon, find a line segment that divides this polygon into two congruent polygons.

You must ensure that this line segment is parallel to the coordinate axes.

Input Format

The first line contains an integer $N$, meaning that the polygon consists of $N$ points.
The next $N$ lines each contain two integers $X_i, Y_i$, representing a vertex of the polygon $(X_i, Y_i)$.

Output Format

If it is impossible to divide it into two congruent polygons, output the string NO.
If it is possible, output four integers $x_1, y_1, x_2, y_2$, representing the segment $(x_1, y_1)\to (x_2, y_2)$.

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

1 2 3 2

Hint

Sample Explanation

For sample $1$, as shown in the figure below, it can be divided into two congruent polygons:

Similarly, outputting 3 2 1 2 is also acceptable.

For sample $2$, as shown in the figure below, it cannot be divided into two congruent polygons:

Constraints and Notes

This problem uses bundled testdata.

• Subtask 1 (12 pts): A solution is guaranteed to exist.
• Subtask 2 (15 pts): $N \le 200$.
• Subtask 3 (23 pts): $N \le 2000$.
• Subtask 4 (50 pts): No special restrictions.

For $100\%$ of the testdata, $4 \le N \le 10^5$.

This problem uses Special Judge.

Note

Translated from BalticOI 2014 Day2 A Demarcation。

Translated by ChatGPT 5