P4423 [BJWC2011] Minimum Triangle

Xaviera has encountered an interesting problem. There are $N$ points on the plane. Xaviera wants to find the triangle with the minimum perimeter. Because there are many points and they are distributed irregularly, Xaviera asks you to solve this problem. To reduce the difficulty, triangles also include three collinear points.

The first line contains an integer $N$ representing the number of points. The next $N$ lines each contain two integers, representing the coordinates of a point.

Output a single line containing the minimum triangle perimeter, rounded to $6$ decimal places.

Constraints: For all testdata, $3 \leq N \leq 2\times 10^5$. Translated by ChatGPT 5