레이팅 미적용You are the engineer in charge of designing a wheel for a new space rover. As you do not have enough time to reinvent the wheel, you decide to copy your predecessor's work and make only one small change.
Looking at the plan, you notice that your predecessor's wheel has the shape of a convex polygon for structural reasons. It is well known that wheels with a larger perimeter roll farther per rotation, so surely they must be superior. You attempt to increase the perimeter by as much as possible by moving a single point on the outside of the wheel. While experimenting, you notice that wheels do not seem to work if they are non-convex or if there is an internal angle below \(90\) degrees.
What is the maximum possible achievable increase in the perimeter of the wheel without violating the above restrictions?
The input consists of:
- One line with an integer \(n\) (\(4 \leq n \leq 10^5\)), the number of points of the wheel.
- \(n\) lines, each with two integers \(x\) and \(y\) (\(\left| x \right|, \left| y \right| \leq 10^5\)), the coordinates of the points.
The points are given in counterclockwise order and form a convex polygon with no internal angle below \(90\) degrees. Note that the convex polygon may contain collinear points, but no two points are at the same position.
Output the maximum possible absolute increase of the perimeter of the wheel.
Your answer should have an absolute or relative error of at most \(10^{-6}\).
5
1 1
4 1
4 3
3 5
1 4
1.594883917346
7
0 -4
3 -3
5 -2
3 2
-6 -2
-6 -4
-2 -4
3.151142198204
4
0 0
1 0
1 1
0 1
0.000000000000