F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
Problem 2458. -- [BeiJing2011]最小三角形

2458: [BeiJing2011]最小三角形

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 1886  Solved: 666
[Submit][Status][Discuss]

Description

Xaviera现在遇到了一个有趣的问题。
平面上有N个点,Xaviera想找出周长最小的三角形。
由于点非常多,分布也非常乱,所以Xaviera想请你来解决这个问题。
为了减小问题的难度,这里的三角形也包括共线的三点。

Input

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

Output

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

Sample Input

4
1 1
2 3
3 3
3 4

Sample Output

3.414214


HINT

100%的数据中N≤200000。

Source

Day1

[Submit][Status][Discuss]

HOME Back