Dividing Points to Maximize Convex Hull Perimeter Sum

Paimon places \(n+1\) distinct points on the plane, one of which is the special point \(O=(0,0)\). The remaining \(n\) points form the set \(\mathbb{S}\). A point set \(\mathbb{U}\) is called a strict convex set if and only if \(|\mathbb{U}|\ge3\) and all points in \(\mathbb{U}\) lie exactly on the convex hull of \(\mathbb{U}\) (with no three collinear).

You are required to partition \(\mathbb{S}\) into two disjoint sets \(\mathbb{A}\) and \(\mathbb{B}\) such that:

• \(\mathbb{A}\cup\mathbb{B}=\mathbb{S}\), and \(\mathbb{A}\cap\mathbb{B}=\emptyset\).
• \(|\mathbb{A}|\ge2\) and \(|\mathbb{B}|\ge2\).
• The sets \(\mathbb{A}\cup\{O\}\) and \(\mathbb{B}\cup\{O\}\) are strict convex sets. Denote their convex hulls by \(C_{\mathbb{A}\cup\{O\}}\) and \(C_{\mathbb{B}\cup\{O\}}\), respectively.
• The outlines (edges) of \(C_{\mathbb{A}\cup\{O\}}\) and \(C_{\mathbb{B}\cup\{O\}}\) intersect only at the point \(O\). That is, \(O\) is the only common point lying on both boundaries.

Your task is to help Paimon choose a valid partition \(\mathbb{A}\) and \(\mathbb{B}\) such that the sum of the perimeters of these two convex hulls, i.e. \[ L\bigl(C_{\mathbb{A}\cup\{O\}}\bigr)+L\bigl(C_{\mathbb{B}\cup\{O\}}\bigr), \] is maximized. Here \(L(\cdot)\) denotes the perimeter of a polygon.

Note: It is guaranteed that the input points (other than \(O\)) are given in general position such that a solution exists. In a valid partition, when you add \(O\) to the points of one part and sort them by their polar angle, the resulting polygon (by joining \(O\) to the first point, then all consecutive points, and finally back to \(O\)) is the convex hull of that set.

inputFormat

The first line contains an integer \(n\) (\(n\ge4\)), the number of points in \(\mathbb{S}\). Each of the following \(n\) lines contains two integers \(x\) and \(y\), representing the coordinates of a point. The special point \(O=(0,0)\) is not given in the input.

outputFormat

Output a single floating point number, representing the maximum possible sum of the perimeters of the two convex hulls. The answer is accepted if its absolute or relative error does not exceed \(10^{-6}\).

sample

4
1 2
2 3
3 1
1 0

13.654179