#P18225. Fragile Pinball

Fragile Pinball

Fragile Pinball

给定一个有 nn 条边的凸多边形。一个很小的弹球可以视为质点,它从多边形内部或边界上的某个位置出发,以恒定的正速率沿直线运动。

你可以在任意时刻瞬间激活多边形的一条边。如果此时弹球恰好位于这条边上,包括边的两个端点,它就会被这条边反射:相对于该边所在的直线,入射角等于反射角。由于边很脆弱,每条边最多只能激活一次。

如果弹球同时位于两条边上,你不能同时激活这两条边,但可以接连激活它们。此时弹球会接连反射两次,运动方向改变两次,而位置和速率保持不变。你也可以只激活其中一条边,或两条都不激活。

弹球本身也很脆弱,最多只能承受 kk 次反射。对于每个 k=0,1,…,nk=0,1,\ldots,n,求弹球能够始终位于凸多边形内部或边界上时,运动路程的最大值。

你可以自由选择弹球的起点和初始运动方向。相邻两次反射可以发生在同一个顶点,此时两次反射之间的路程为零。

输入格式

第一行包含一个整数 nn,表示凸多边形的顶点数。

接下来 nn 行,第 ii 行包含两个整数 xi,yix_i,y_i,表示第 ii 个顶点的坐标。

保证顶点按逆时针顺序给出,且任意三个顶点不共线。

输出格式

输出 n+1n+1 行。第 ii 行输出一个实数,表示最多发生 i−1i-1 次反射时,弹球能够运动的最大路程。

答案的绝对误差或相对误差不超过 10−610^{-6} 即可。形式化地,设你的输出为 aa,标准答案为 bb,当且仅当

∣a−b∣max⁡(1,∣b∣)≤10−6\frac{|a-b|}{\max(1,|b|)}\le 10^{-6}

时,该答案被接受。

样例一

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

样例说明

下图给出两个样例中 k=0,1,2,3k=0,1,2,3 时的最优路径,红色折线表示弹球的运动路径。

两个样例在不同反射次数下的最优路径

数据范围

对于所有数据:

  • 3≤n≤63\le n\le 6;
  • −100≤xi,yi≤100-100\le x_i,y_i\le100;
  • 所有坐标均为整数;
  • 顶点按逆时针顺序构成凸多边形,任意三个顶点不共线。

本题只有一组输入数据。