题目描述

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

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

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

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

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

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

形式化地说：

设在某一时刻碎片系统绕 $O$ 点的旋转角度为 $\theta$，第 $i$ 个碎片的位置为 $(x_i',y_i')$，定义此时观测框的周长为：

$$P(\theta) = 2 \times \left(\max_{i=1}^n x_i' - \min_{i=1}^n x_i'\right) + 2\times \left(\max_{i=1}^n y_i' - \min_{i=1}^n y_i'\right)$$

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

$$\lim_{T\to +\infty} \dfrac{1}{T} \int_{0}^T P(\theta) \mathrm{d}\theta$$

输入格式

输入包含多组测试数据。

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

下面是 $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$ 个恒星碎片的初始坐标 $P_i(x_i,y_i)$。保证单组数据内，碎片的坐标两两不同。

保证单个测试点内，所有测试数据的 $n$ 之和不超过 $2 \times 10^5$。

输出格式

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

注意，当你的答案与标准答案的相对误差或绝对误差不超过 $10^{-6}$ 时，视为正确。

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

2.546479089470
12.732395447352
4.347111721785
12.123088271684
16.470199993469
509311738.569670943427

提示

对于第一组数据，可以计算得出观测框周长期望值的精确数值为 $\frac{8}{\pi}$。

对于第二组数据，可以计算得出观测框周长期望值的精确数值为 $\frac{40}{\pi}$。