Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register
ACM ICPC 2018 World Finals
Language:
The Biggest Cake
 Time Limit: 5000MS Memory Limit: 65536K Total Submissions: 3402 Accepted: 607

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.

Sample Input

```1
4
0 0
1 0
1 1
3 1
```

Sample Output

`3.536`

Source

[Submit]   [Go Back]   [Status]   [Discuss]