#P3587. The Biggest Cake

    ID: 2597 远端评测题 5000ms 64MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>South Central China 2008 hosted by NUDT

The Biggest Cake

Description

In the kingdom of Polygon the royal family consists of the king, the queen, and the 10-year-old twins, Prince Obtuse and Prince Trisect. The twins are fiercely competitive, and on their birthday they always vie with each other for the biggest portion of the cake. The wise king and queen have devised the following way to prevent squabbles over the cake. The King randomly selects some points in the same plane, and then the prince will be given the chance to select three different points from them to make a triangle. The circumcircle of the triangle would be the shape of the cake for him. Now one of the little princes asks you for help. Your task is to help the little prince to find the biggest cake he can get.

Input

The first line of the input is an integer T which indicates the number of test cases. The first line of each test case is an integer n, denoting the number of points.3 ≤ n ≤ 655. The following n lines describe coordinates of points. 0 ≤ x, y ≤ 10000.

Output

For each test case, output radius of the biggest cake given with accuracy 10-3 in a single line.

1
4
0 0
1 0
1 1
3 1
3.536

Source

South Central China 2008 hosted by NUDT