F. Maximize the Ratio
time limit per test
5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

In geometry, a convex polygon is a simple polygon (which is not self-intersecting) in which no segment joining a point to another one on the boundary goes outside the polygon. Equivalently, it is a simple polygon whose interior is a convex set.

Given $$$n$$$ distinct points on the plane, you may draw some segments such that:

  • At least one segment is drawn.
  • The length of each segment is positive and finite.
  • Each endpoint of any segment belongs to the given set of points.
  • For any two segments, they either share an endpoint or have no intersection.
  • All segments form a convex polygon.

Let the area of the polygon be $$$A$$$, and let the sum of the squares of the lengths of segments be $$$B$$$. Your task is to maximize the ratio of $$$A$$$ to $$$B$$$.

Input

The first line contains an integer $$$T$$$ $$$(1 \leq T \leq 10)$$$, indicating the number of test cases. Then $$$T$$$ test cases are following.

For each test case: the first line contains an integer $$$n$$$ $$$(3 \leq n \leq 500)$$$ indicating the number of given points. In the next $$$n$$$ lines, each line contains two integers $$$x$$$ and $$$y$$$ $$$(-10^4 \leq x, y \leq 10^4)$$$ representing a point at $$$(x, y)$$$.

For all points in an individual test case, it is guaranteed that no two points are identical and no three points are collinear. It is also guaranteed that the sum of $$$n$$$ in all test cases is up to $$$500$$$.

Output

For each test case, output the maximal ratio of $$$A$$$ to $$$B$$$ in a single line. Your answer is acceptable if its absolute or relative error does not exceed $$$10^{-9}$$$.

Formally speaking, suppose that your output is $$$a$$$ and the jury's answer is $$$b$$$. Your output is accepted if and only if $$$\frac{|a - b|}{\max(1, |b|)} \leq 10^{-9}$$$.

Example
Input
2
4
0 0
0 5
5 5
5 0
4
0 0
0 5
5 0
2 2
Output
0.250000000000000
0.125000000000000