eolymp
bolt
Try our new interface for solving problems
Problems

Grand Center

Grand Center

There is no generally accepted standard of calculating the center point of some territory. This fact is widely used to promote different places. You can always find a meaning for the word ``center'', according to which your city would be the center of the country! Gloria decided to develop one universal standard and find the true center. Consider any point inside a convex polygon, and any direction. There is a unique segment that passes through the point, is parallel to the direction, and has both ends on the boundary of the polygon. The point divides the segment into two parts. The {\it direction imbalance} is defined as the ratio of the length of the bigger part to the length of the smaller part. The {\it imbalance} of the point is the maximum direction imbalance over all directions. Gloria finds this value interesting, and wants to define the {\it Grand center} of a convex polygon as the point inside it which has the minimum possible imbalance. Help her to calculate the imbalance of the Grand center of a given polygon. \InputFile The first line contains a single integer $n$~--- the number of vertices of the given convex polygon ($3 \le n \le 10\,000$). The $i$-th of the following $n$ lines contains two integers $x_i$ and $y_i$~--- the coordinates of the $i$-th polygon vertex ($-10^5 \le x_i, y_i \le 10^5$). The $x$-axis runs from left to right, and the $y$-axis runs from bottom to top. The vertices are numbered in counterclockwise order. The polygon is strictly convex: all internal angles of the polygon are strictly smaller than $\pi$. \OutputFile Print one real number~--- the imbalance of the Grand center of the given polygon. Your answer will be considered correct if its absolute or relative error doesn't exceed $10^{-6}$. \Note The following pictures illustrate all three example tests: \begin{center} \begin{tabular}{c@{\hskip 2cm}c@{\hskip 2cm}c} \includegraphics{center.1} & \includegraphics{center.2} & \includegraphics{center.3} \end{tabular} \end{center} In the first example test, for the center of the square, the direction imbalance is equal to $1$ for any direction, i.e. any segment is split into two equal parts. In the second example test, it's well-known that the median intersection point of a triangle splits the medians in a $2:1$ ratio. In the given triangle, the medians define the most imbalanced directions for that point. For any other point, the imbalance is even bigger. In the third example test, the Grand center is located at $(1.6, 1.6)$.
Time limit 1 second
Memory limit 512 MiB
Input example #1
4
0 0
1 0
1 1
0 1
Output example #1
Input example #2
3
0 0
1 0
0 1
Output example #2
Input example #3
4
0 0
2 0
4 4
0 2
Output example #3
Author Pavel Kunyavskiy