qcjj 正在给大家寄喜糖,她会关注快递的途径点。 1. 初始时,qcjj 会把 快递出发地 以最大比例尺展示在屏幕中央。 2. 然后,沿着当前位置与下一个途经点的连线移动屏幕,每 个单位长度需要滑动 秒,直到下一个途经点。 3. 重复步骤 2 ,直到到达终点。 由于在最大比例尺下滑动的耗时巨大,qcjj 会选择在每次滑动前缩小比例尺,在每次滑动后放大比例尺至最大。 缩小 秒后,两点间距离 会变为 ,放大回去也需要 秒, 可以是浮点数。 给你 个点的坐标,请你帮 qcjj 找一个最短耗时的屏幕滑动方案。 形式化题面: 给定 个点,每个相邻点对之间有一个欧式距离 ,耗时为 。 你需要最小化 ,并输出之。 其中, 是你自己选定的非负浮点数,对于不同的 可以有不同的 。
输入描述:
第一行输入一个整数 ,代表途径点的数量。随后 行,每行两个浮点数 和 ,保证小数点后有六位。第一个点是起点,最后一个点是终点。
输出描述:
输出该次查询的最小总耗时,你需要保证相对浮点误差不超过 。
示例1
输入
7
116.427738 40.006073
116.422292 40.003368
116.592792 40.124332
116.345299 39.680634
121.474168 31.250638
121.524219 31.058688
121.533136 31.243885
示例2
输入
4
115.975450 29.544970
119.511818 39.823899
119.726584 39.973635
110.496858 47.917480
加载中...