Axis-Aligned Polygon Bisection

Given a polygon with n vertices provided in order, find an axis‐aligned line segment (i.e. parallel to the x- or y-axis) that splits the polygon into two congruent parts. It is guaranteed that the polygon is symmetric with respect to either a vertical line or a horizontal line. In other words, if the polygon is symmetric about the vertical line \(x=\frac{\min(x)+\max(x)}{2}\), then the segment along this line which has its endpoints at the intersection of the line with the polygon is a valid answer. Otherwise, if it is symmetric about the horizontal line \(y=\frac{\min(y)+\max(y)}{2}\), you should output the segment along that line.

Input Format:

• The first line contains an integer \(n\), the number of vertices of the polygon.
• The following \(n\) lines each contain two space‐separated numbers representing the coordinates \(x\) and \(y\) of the vertices, given in order.

Output Format:

• Output four numbers: either \(x\, y_{1}\, x\, y_{2}\) if using a vertical division or \(x_{1}\, y\, x_{2}\, y\) if using a horizontal division. These represent the coordinates of the endpoints of the dividing segment.

Note: The segment must be parallel to one of the coordinate axes and exactly split the polygon into two congruent parts. It is guaranteed that such a segment exists for the provided polygon.

inputFormat

The input begins with an integer n indicating the number of vertices. The next n lines each contain two space-separated numbers representing the coordinates of the vertices in order.

outputFormat

Output four numbers representing the two endpoints of the line segment that divides the polygon into two congruent parts. If the division is vertical, the format should be:

x y1 x y2

If horizontal, output:

x1 y x2 y

sample

4
0 0
4 0
4 2
0 2

2.0 0.0 2.0 2.0