Problem Description

In a certain galaxy observation plan, an observatory records the initial positions of $n$ star fragments on a 2D plane. The position of the $i$-th fragment is $P_i(x_i,y_i)$.

Due to the influence of a central gravitational source, these fragments rotate uniformly around the galaxy center $O(0,0)$ with the same angular velocity. At any moment, all points have the same rotation angle with respect to the origin.

The observatory uses an observation frame to continuously observe these fragments. The frame satisfies:

• The frame is an axis-aligned rectangle (all sides are parallel to the coordinate axes).
• The frame must completely cover the positions of all fragments.
• The frame does not have to cover the galaxy center $O(0,0)$.
• Among all frames that satisfy the coverage requirement, choose the one with the minimum perimeter.

As time goes by, the fragments keep rotating, and the size of the observation frame changes accordingly. The energy consumption rate of the observation system at that moment is proportional to the perimeter of the observation frame.

To reasonably estimate the energy consumption of the observation system, you plan to estimate it using the perimeter of the observation frame. As the observation time increases, the average value of the frame perimeter will approach a certain value, and your task is to compute this value.

Formally:

Suppose that at some moment the fragment system has rotated by angle $\theta$ around point $O$, and the position of the $i$-th fragment is $(x_i',y_i')$. Define the perimeter of the observation frame at this time as:

$$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)$$

Your task is to compute the following value:

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

Input Format

The input contains multiple test cases.

The first line contains an integer $t$ ($1\le t\le 10^5$), indicating the number of test cases.

Then follow $t$ test cases. For each test case:

The first line contains an integer $n$ ($2 \le n \le 2 \times 10^5$), indicating the number of star fragments.

The next $n$ lines each contain two integers $x_i, y_i$ ($-10^8 \le x_i, y_i \le 10^8$), indicating the initial coordinates $P_i(x_i,y_i)$ of the $i$-th star fragment. It is guaranteed that within a single test case, all fragment coordinates are pairwise distinct.

It is guaranteed that within a single test point, the sum of $n$ over all test cases does not exceed $2 \times 10^5$.

Output Format

For each test case, output a real number, representing the average value of the observation frame perimeter.

Note that your answer is considered correct if its relative error or absolute error does not exceed $10^{-6}$ compared to the standard answer.

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

Hint

For the first group of data, the exact value of the expected observation frame perimeter can be computed as $\frac{8}{\pi}$.

For the second group of data, the exact value of the expected observation frame perimeter can be computed as $\frac{40}{\pi}$.

Translated by ChatGPT 5