4512 - 最小三角形

Xaviera 现在遇到了一个有趣的问题。

平面上有 N 个点,Xaviera 想找出周长最小的三角形。

由于点非常多,分布也非常乱,所以 Xaviera 想请你来解决这个问题。

为了减小问题的难度,这里的三角形也包括共线的三点。

输入

第一行包含一个整数 N 表示点的个数。

接下来 N 行每行有两个整数,表示这个点的坐标。

输出

输出只有一行,包含一个 6 位小数,为周长最短的三角形的周长(四舍五入)。

样例

输入

4
1 1
2 3
3 3
3 4

输出

3.414214

提示

对于所有数据,3 \leq N \leq 2\times 10^5

来源

BJWC

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题