#P18225. Fragile Pinball
Fragile Pinball
Fragile Pinball
给定一个有 条边的凸多边形。一个很小的弹球可以视为质点,它从多边形内部或边界上的某个位置出发,以恒定的正速率沿直线运动。
你可以在任意时刻瞬间激活多边形的一条边。如果此时弹球恰好位于这条边上,包括边的两个端点,它就会被这条边反射:相对于该边所在的直线,入射角等于反射角。由于边很脆弱,每条边最多只能激活一次。
如果弹球同时位于两条边上,你不能同时激活这两条边,但可以接连激活它们。此时弹球会接连反射两次,运动方向改变两次,而位置和速率保持不变。你也可以只激活其中一条边,或两条都不激活。
弹球本身也很脆弱,最多只能承受 次反射。对于每个 ,求弹球能够始终位于凸多边形内部或边界上时,运动路程的最大值。
你可以自由选择弹球的起点和初始运动方向。相邻两次反射可以发生在同一个顶点,此时两次反射之间的路程为零。
输入格式
第一行包含一个整数 ,表示凸多边形的顶点数。
接下来 行,第 行包含两个整数 ,表示第 个顶点的坐标。
保证顶点按逆时针顺序给出,且任意三个顶点不共线。
输出格式
输出 行。第 行输出一个实数,表示最多发生 次反射时,弹球能够运动的最大路程。
答案的绝对误差或相对误差不超过 即可。形式化地,设你的输出为 ,标准答案为 ,当且仅当
时,该答案被接受。
样例一
3
4 0
0 3
0 -1
5.000000000000000000
8.000000000000000000
8.868185038797563409
12.210024810881955830
样例二
3
4 0
0 3
0 2
5.000000000000000000
5.366563145999495272
6.111919138499425171
6.782203304416628317
样例说明
下图给出两个样例中 时的最优路径,红色折线表示弹球的运动路径。

数据范围
对于所有数据:
- ;
- ;
- 所有坐标均为整数;
- 顶点按逆时针顺序构成凸多边形,任意三个顶点不共线。
本题只有一组输入数据。