26410번 - Intersection Of Tangents 스페셜 저지다국어

In this problem polygons are assumed to have no self-touchings or self-intersections.

A tangent to a polygon is a straight line that contains at least one point on the boundary of the polygon, and none of its interior points.

You are given a polygon with integer vertex coordinates. The polygon is not necessarily convex. Find a point with integer coordinates such that there exist two tangents to this polygon which both pass through this point and intersect at 90$^{\circ}$. It is guaranteed that at least one solution exists. If there are multiple solutions, output any of them.

The first line of input contains a single integer $n$ ($3 \leq n \leq 1000$) --- the number of vertices in the polygon.

$n$ lines follow describing the vertices of the polygon. $i$-th of them contains two integers $x_i$ and $y_i$ ($-10^8 \leq x_i, y_i \leq 10^8$) --- the coordinates of $i$-th vertex. The vertices are given in counter-clockwise order.

The polygon has no self-touchings or self-intersections. There are no three consecutive points which lie on the same line.

It is guaranteed that an answer exists.

Output two integers $x$ and $y$ ($-10^9 \leq x, y \leq 10^9$) --- the coordinates of the point you found.

Images for samples and some random photo.