Divide a Convex
Description
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 properties: 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.
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)$.
- $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 length of the shortest line segment that divides the input convex polygon into two equiperimeter convex polygons.
The answer is considered correct if the precision error is less than $10^{-6}$.
Input
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)$.
- $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.
Output
The length of the shortest line segment that divides the input convex polygon into two equiperimeter convex polygons.
The answer is considered correct if the precision error is less than $10^{-6}$.
4
0 0
1 10
0 10
1 0
5
0 0
10 10
0 10
10 0
5 11
1
10.0