| 题目名称 | 1510. [Ural 1143] 青蛙的烦恼 |
|---|---|
| 输入输出 | frogpuzzle.in/out |
| 难度等级 | ★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 8 |
| 题目来源 |
 王梦迪
于2014-01-28加入修改该题
|
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：100， 提交：165， 通过率：60.61% | ||||
|
SM |
100 | 0.000 s | 0.00 MiB | C++ |
|
董博文 |
100 | 0.000 s | 0.00 MiB | C++ |
|
董博文 |
100 | 0.000 s | 0.00 MiB | C++ |
|
AntiLeaf |
100 | 0.000 s | 0.00 MiB | C++ |
|
许子康 |
100 | 0.000 s | 0.00 MiB | C++ |
|
Yniverse |
100 | 0.000 s | 0.00 MiB | C++ |
|
Dilain |
100 | 0.000 s | 0.00 MiB | C++ |
|
Yniverse |
100 | 0.000 s | 0.00 MiB | C++ |
|
Yniverse |
100 | 0.000 s | 0.00 MiB | C++ |
|
AntiLeaf |
100 | 0.000 s | 0.00 MiB | C++ |
| 关于 青蛙的烦恼 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
| ||||
|
| ||||
|
| ||||
|
| ||||
|
| ||||
|
| ||||
|
| ||||
|
| ||||
|
| ||||
|
| ||||
【题目描述】
池塘里有n片荷叶（1<=n<=60），它们正好形成一个凸多边形。按照逆时针方向将这n片荷叶顺次编号为1,2,...,n。
有一只小青蛙站在1号荷叶上，它想跳过每片荷叶一次且仅一次（它可以从所站的荷叶跳到另外任意一片荷叶上）。同时，它又希望跳过的总距离最短。
请你编程帮助小青蛙求出最短的路线长度。
【输入格式】
第一行为整数n，荷叶的数量。
接下来n行，每行两个实数，为n个多边形的顶点坐标，按照逆时针方向给出。保证不会爆double。
【输出格式】
遍历所有荷叶最短路程，请保留3位小数，无Checker。
【样例输入】
4
50.0 1.0
5.0 1.0
0.0 0.0
45.0 0.0
【样例输出】
50.211
【来源】
刘汝佳，黄亮，《算法艺术与信息学竞赛》P133