新年趣事之红包

新年趣事之红包

测试数据来自 system/1069

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

描述

xiaomengxian一进门,发现外公、外婆、叔叔、阿姨……都坐在客厅里等着他呢。经过仔细观察,xiaomengxian发现他们所有人正好组成了一个凸多边形。最重要的是,他们每个人手里都拿着一个红包(^o^)。于是非常心急,xiaomengxian决定找一条最短的路线,拿到所有的红包。

假设屋里共有N个人拿着红包,把他们分别从1到N编号。其中,编号为1的人就坐在大门口,xiaomengxian必须从这里出发去拿其它的红包。一条合法的路线必须经过所有的点一次且仅一次。

格式

输入格式

第一行为一个整数N(1<=N<=800)。

以下N行,每行两个实数Xi,Yi,表示该点的坐标。

各个点按照逆时针顺序依次给出。

输出格式

一个实数,表示最短的路线长度(保留三位小数)。

样例1

样例输入1

4
50.0 1.0
5.0 1.0
0.0 0.0
45.0 0.0

样例输出1

50.211

限制

各个测试点1s

来源

Xiaomengxian

比赛18

未参加
状态
已结束
规则
OI
题目
6
开始于
2023-07-09 12:00
结束于
2023-07-10 13:00
持续时间
25.0 小时
主持人
参赛人数
1