10144: 雷达

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:1 Solved:0

Description

国王张静静的国家发生了战乱。为了平定战乱,张静静开发出一种新型的雷达,要用这种雷达来侦测一个平面上的 n 个飞机的动向。

假设雷达安装在 O(x0,y0) 位置,n 个飞机坐落在 P1(x1,y1),P2(x2,y2),...,Pn(xn,yn) 。雷达对于每个 Pi(i=1,2,3,...,n) ,会侦测该位置的飞机是否跟雷达的距离发生变化,如果变化,雷达就会报警。

为了做到这一点,张静静的雷达的工作原理是这样的:雷达对于每个 Pi(i=1,2,3,...,n) 会发出一种神奇的物质 Ω ,布满以 O 为圆心,以 OPi 为半径的球表面(这个球有一半是在底下的,雷达实际发出 Ω 布满的部分是球表面积的一半)。如果飞机穿过了 Ω 层,雷达就会得到反馈。

注意,雷达是不够智能的,即使O 距离几个敌军飞机距离相同,Ω 层也不会共用。

所以张静静的问题就是,如何合理的安排雷达的位置,使得 Ω 层总面积最小?

Input

测试数据有多组,数据第一行包含测试数据的数目 T(≤10) 。

每组数据第一行包含一个整数 n(1≤n≤100000),意义见题目描述。

接下来 n 行,第 i(i=1,2,3,...,n) 行有两个数 (xi,yi) 表示第 i 个飞机的位置坐标。

数据保证不会有两个飞机的距离小于 0.001 。

Output

对于每组测试数据,输出 v于一行,表示最小的花费,保留小数点后三位小数。

Sample Input Copy

1
2
1 1
2 2

Sample Output Copy

6.283