시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 1024 MB4000.000%

문제

Ivan likes painting. He decided to paint a sun.

To do that, he took $n$ points with integer coordinates on the plane. Ivan will draw segments connecting some pairs of points to get the best sun.

  • Ivan will connect exactly $n$ pairs of points with segments between them.
  • All segments should not intersect (except for endpoints).
  • There should be exactly one cycle. This cycle should be a convex polygon.
  • Each point that is not one of the polygon vertices should lie outside of the polygon and should be connected with one of the polygon's vertices.
  • It is possible that all vertices will lie on the cycle.

Ivan wants to paint a bright, pretty sun. So he came up with the score of the sun:

  • Let us define $S$ as the area of the polygon.
  • Let us define $P$ as the sum of lengths of all drawn segments.
  • The value $\displaystyle \frac{S}{P}$ is the score of the sun.

What is the maximum possible score of the sun?

입력

The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) --- the number of test cases. Description of test cases follows.

The first line of each test case contains a single integer $n$ ($3 \leq n \leq 300$) --- the number of points.

Each of the next $n$ lines contains two integers $x_i$, $y_i$ ($|x_i|, |y_i| \leq 10^6$). All points are different. No three points lie on the same line.

It is guaranteed that the sum of $n^2$ for all test cases does not exceed $90\,000$.

출력

For each test case, print a single real number --- the maximum possible score of the sun that can be drawn.

The absolute or relative error should not exceed $10^{-6}$.

예제 입력 1

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

예제 출력 1

0.3090169943749474
1.2368614277111258
0.2711375415034555
1.5631002094915825

노트

The picture of the sun with the maximum score in the fourth test case:

For this sun, $S = 64$, $P = 32 + 4\sqrt{5}$, so its score is $\displaystyle \frac{64}{32+4\sqrt{5}}$.