I. 星系观测计划
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

在某星系观测计划中，天文台记录了 $$$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 $$$$$$

Input

输入包含多组测试数据。

第一行包含一个整数 $$$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$$$。

Output

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

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

Example
Input
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
Output
2.546479089470
12.732395447352
4.347111721785
12.123088271684
16.470199993469
509311738.569670943427
Note

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

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