logo AlgoBeat OnlineJudge
登录 注册

#216707. [SCCPC 2026] 星系观测计划

内存限制:1024 MiB 时间限制:2000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

在某星系观测计划中,天文台记录了 个恒星碎片在二维平面中的初始位置,其中第 个碎片的位置为

受到中心引力源的影响,这些碎片会绕星系中心 以相同的角速度进行匀速旋转,且任意时刻所有点相对于原点的旋转角度相同。

天文台使用一个观测框对这些碎片进行持续观测,该观测框满足如下条件:

  • 观测框为一个各边平行于坐标轴的矩形;
  • 观测框必须完全覆盖所有碎片的位置;
  • 观测框不必覆盖星系中心
  • 在所有满足覆盖条件的观测框中,选取周长最小的那个。

随着时间的推移,碎片不断旋转,观测框的大小也随之变化,观测系统在该时刻的能量消耗速率与观测框的周长成正比。

为了合理估计观测系统的能量消耗,你打算通过观测框周长对能量消耗进行估计。随着观测时间的增加,观测框周长的平均值会趋于某个值,你的任务是计算这个值。

形式化地说:

设在某一时刻碎片系统绕 点的旋转角度为 ,第 个碎片的位置为 ,定义此时观测框的周长为:

你的任务是计算下面的值:

输入格式

输入包含多组测试数据。

第一行包含一个整数 ),表示测试数据的组数。

下面是 组数据,对于每组测试数据:

第一行包含一个整数 ),表示恒星碎片的数量。

接下来的 行,每行包含两个整数 ),表示第 个恒星碎片的初始坐标 。保证单组数据内,碎片的坐标两两不同。

保证单个测试点内,所有测试数据的 之和不超过

输出格式

对于每组测试数据,输出一个实数,表示观测框周长的平均值。

注意,当你的答案与标准答案的相对误差或绝对误差不超过 时,视为正确。

样例

样例输入 1

6
2
0 0
1 0
4
0 0
0 2
0 3
0 5
3
0 0
1 0
0 1
5
0 0
1 0
2 0
3 1
4 -1
8
1 1
2 1
1 2
-1 1
-1 -1
2 -1
0 0
-2 -2
3
-100000000 100000000
100000000 98765432
12345678 100000000

样例输出 1

2.546479089470
12.732395447352
4.347111721785
12.123088271684
16.470199993469
509311738.569670943427

数据范围与提示

对于第一组数据,可以计算得出观测框周长期望值的精确数值为

对于第二组数据,可以计算得出观测框周长期望值的精确数值为