[2026 CCPC_NC_I J] 贪吃蛇
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
Description
夏天到了,又到了蛇蛇出来觅食的季节。
蛇蛇生活的地方可以看成一个二维平面,它位于原点 。平面上有 个食物,第 个食物位于整数坐标 ,保证没有食物位于原点。
蛇蛇的觅食方式很特殊:
- 先选择一个以原点为圆心的角度区间 ;
- 以原点为顶点,张开一个以该区间为圆心角的扇形,并且扇形会不断向外扩展,直到将该角度区间内(包含边界)的所有食物全部一口吞下。
扇形的面积大小就是蛇蛇本顿觅食消耗的能量。
蛇蛇现在很饿,它想知道,想要一口吃掉至少 个食物,所需的最少能量是多少?
Format
Input
第一行一个整数 (),表示测试数据组数。保证所有测试数据的 之和不超过 。
对于每组数据:
第一行两个整数 (),分别表示食物总数和至少需要吃掉的食物数量。
接下来 行,每行两个整数 (),表示第 个食物的坐标。保证 。
Output
对于每组数据,输出一行一个实数,表示最少所需能量。
当你的输出与标准答案的绝对误差或相对误差不超过 时即被视为正确。
Samples
2
1 1
1 2
3 2
0 2
1 0
-1 -1
0.000000000000
2.356194490192
Note
对于第一组数据,只有一个食物且 ,选择的角度区间恰好只包含该食物的方向,扇形退化为从原点出发的线段,面积为 。
对于第二组数据,最优策略为覆盖食物 和 ,最少能量是 $\frac{1}{2}\times \frac{3\pi}{4}\times 2=\frac{3\pi}{4}$。
2026CCPC南昌邀请赛暨江西省赛(unofficial)
- Status
- Done
- Rule
- XCPC
- Problem
- 13
- Start at
- 2026-9-30 13:30
- End at
- 2026-9-30 17:30
- Duration
- 4 hour(s)
- Host
- Partic.
- 2