B · Bread：中文题面

本场总览 · QOJ 原题

时限 1 秒，内存限制 512 MB。中文内容依据本次提供的题面整理；以原题为准。

中文题面 #

一块面包视为平面上的凸多边形，顶点 $A_1,\ldots,A_n$ 按逆时针排列，顶点互异且任意三点不共线。地面是 $y=0$。初始边 $(A_n,A_1)$ 接触地面，$A_n=(0,0)$，$A_1=(x_1,0)$ 且 $x_1>0$。

面包向 $x$ 轴正方向滚动。第 $i$ 次转动以当前的 $A_{((i-1)\bmod n)+1}$ 为中心顺时针旋转，直到下一个顶点 $A_{(i\bmod n)+1}$ 第一次接触地面。

第 $k$ 次转动结束时，$L(k)$ 是原点到此时 $A_{(k\bmod n)+1}$ 的距离；$S(k)$ 是从第一次转动开始到此时，多边形覆盖过的所有区域的并集面积。求

$\lim_{k\to+\infty}\frac{S(k)}{L(k)}.$

重叠部分只计一次，不能把每次转动扫过的面积直接相加；也不要把 $L(k)$ 换成某个顶点的运动轨迹长度。

输入、输出与约束 #

$1\le T\le10^3$。每组先输入 $3\le n\le10^5$，再输入 $n$ 个整数坐标 $(x_i,y_i)$，其中 $|x_i|\le10^9$、$0\le y_i\le10^9$。保证 $y_1=x_n=y_n=0$、$x_1>0$，并满足上述凸性和顺序条件；所有测试的 $\sum n\le3\times10^5$。

每组输出一个浮点数。设输出为 $a$、标准答案为 $b$，要求 $|a-b|/\max\{b,1\}\le10^{-9}$。

样例 #

输入 1 #

2
3
2 0
1 5
0 0
4
1 0
1 1
0 1
0 0

输出 1 #

4.908664519941197
1.384172075579563

样例说明 #

两组分别给出三角形与单位正方形，输出都是滚动次数趋于无穷时的比值。第一组三角形在 $k=4$ 时有 $L(4)=4+3\sqrt{26}$，而 $S(4)=120/13+13\sqrt3+91\pi/6+43\arctan(1/5)$；这个有限步比值不应直接等同于样例输出的极限。

整理进度 #

本批材料没有这道题的个人 C++ 文件，因此这里先保留中文题面与样例解释；不把题面整理记作已补题。赛时提交过程与赛后补题记录待补。