Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
The Biggest Cake
Time Limit: 5000MSMemory Limit: 65536K
Total Submissions: 3359Accepted: 599

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]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator