| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 (추가 시간 없음) | 1024 MB | 4 | 0 | 0 | 0.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 wants to paint a bright, pretty sun. So he came up with 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}$.
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
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}}$.