P15920 [TOPC 2023] Divide a Convex

A polygon is a geometric shape that consists of a closed set of straight line segments connected end-to-end to form a closed loop. These line segments enclose a region of space called the polygon’s interior. The points where the line segments meet are called *vertices*, and the line segments themselves are called *edges*. A simple polygon is a polygon that has no self-intersecting edges and has no holes. In other words, none of its edges cross over or intersect with each other within the interior of the polygon, and at each of its vertex, exactly two of its edges meet. A convex polygon is a specific type of simple polygon that has an additional property: All interior angles are strictly less than 180 degrees. In a convex polygon, if you were to draw straight lines connecting any two points inside the polygon, those lines would always remain inside the polygon. David has a land with a convex polygon shape that has $n$ vertices $(x_1, y_1), \dots, (x_n, y_n)$. He wants to divide the land into two parts by a line segment $\overline{PQ}$ satisfying the following criteria. - $P$ and $Q$ are points located on different edges of the convex polygon to be divided. - The two parts are convex polygons with an equal perimeter. That is, the sum of the lengths of the first part’s edges equals the sum of the lengths of the second part’s edges. Please help David to find out the minimum length of $\overline{PQ}$.

The first line contains an integer $n$ indicating the number of vertices of the convex polygon to be divided. The $i$-th of the following $n$ lines contains two space-separated integers $x_i$ and $y_i$ indicating that a vertex of the convex polygon is at the point $(x_i, y_i)$.

The length of the shortest line segment that divides the input convex polygon into two equiperimeter convex polygons.

- $n \le 100000$ - $x_i, y_i \in [-10^8, 10^8]$ for $1 \le i \le n$. - There is no guarantee $\overline{(x_i, y_i)(x_{i+1}, y_{i+1})}$ will be an edge. - The answer is considered correct if the precision error is less than $10^{-6}$.