问题1236--全自动分身!

1236: 全自动分身!

[命题人 : ]
时间限制 : 4.000 sec  内存限制 : 128 MB

题目描述

题目背景

普通的分身术已经无法满足Rolnan了,他现在研究出了全自动分身术!

题目描述

一开始,Rolnan会分裂为 \(n\) 个细胞,每个细胞位于一个平面坐标系的 \((x_i,y_i)\) 位置。

开始计时后,每个细胞会以每秒 \(0.5\) 的速度圆形扩展,现在Rolnan想要变回人形,他需要所有的细胞都彼此连通,请你求出这个时间。

输入

第一行一个整数 \(T(1\leq T\leq 5)\) 表示数据的组数。

接下来每组数据,第一行一个整数 \(n(2\leq n \leq 5000)\),接下来 \(n\) 行,每行两个整数 \(x_i,y_i(|x_i|,|y_i|\leq 10^9)\)。

输出

请你求出Rolnan的所有细胞连通的最早时间的平方

样例输入 Copy

2
3
0 0
1 1
0 1
5
1 1
4 5
1 4
2 6
3 10

样例输出 Copy

1
17

提示

注意本题的空间限制!