1012. Shift Square

题目描述

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

$$P_i\{x_i,y_i\}。$$

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

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

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

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

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

形式化地说： 设在某一时刻碎片系统绕 $O$ 点的旋转角度为 $\theta$，第 $i$ 个碎片的位置为 \{x_i',y_i'\}，其中

x_i'=x_i\cos\theta-y_i\sin\theta, y_i'=x_i\sin\theta+y_i\cos\theta。

定义此时所有点的横向宽度和纵向高度分别为

$$W\{\theta\}=\max_{i=1}^{n}x_i'-\min_{i=1}^{n}x_i',$$$$H\{\theta\}=\max_{i=1}^{n}y_i'-\min_{i=1}^{n}y_i'。$$

由于观测框必须是正方形，所以最小正方形的边长为

$$L\{\theta\}=\max\{W\{\theta\},H\{\theta\}\}。$$

因此该时刻观测框的周长为

$$Q\{\theta\}=4L\{\theta\}。$$

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

$$\lim_{T\to+\infty}\frac{1}{T}\int_0^T Q\{\theta\}\ d\theta。$$

输入格式

输入包含多组测试数据。

第一行包含一个整数 $t（1\le t\le 10）$，表示测试数据的组数。

下面是 $t$ 组数据，对于每组测试数据：

第一行包含一个整数 $n（2\le n\le 2\times 10^5,）$，表示恒星碎片的数量。

接下来 $n$ 行，每行包含两个整数 $x_i,y_i（-10^8\le x_i,y_i\le 10^8）$，表示第 $i$ 个恒星碎片的初始坐标。

保证同一组测试数据内，所有点两两不同。

输出格式

对于每组测试数据，输出一行一个实数，表示观测框周长的长期平均值。 当你的答案与标准答案的相对误差或绝对误差不超过 $10^{-6}$ 时，视为正确。

样例输入

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

样例输出

3.601265264628424
18.006326323142121
5.092958178940651

提示

对于第一组数据，两个点之间的距离为 $1$。 旋转过程中，最小正方形的边长为

$$\max\{|\cos\theta|,|\sin\theta|\},$$

所以平均周长为

$$\frac{1}{2\pi}\int_0^{2\pi}4\max\{|\cos\theta|,|\sin\theta|\},d\theta \frac{8\sqrt 2}{\pi} \approx 3.601265264628。$$

来源：2026杭电多校-测试专用（四川大学） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1231&pid=1012 ⚠ 本题为 Special Judge。官方数据中的 .out 多为评测机判定输出（如 AC/OK/Correct/yes），导入后需自行提供 checker 方可正确评测。