Ivan aime peindre. Il a décidé de peindre un soleil. Pour ce faire, il a pris $n$ points avec des coordonnées entières dans le plan. Ivan va tracer des segments reliant certaines paires de points pour obtenir le meilleur soleil.
- Ivan reliera exactement $n$ paires de points avec des segments entre eux.
- Tous les segments ne doivent pas se croiser (sauf aux extrémités).
- Il doit y avoir exactement un cycle. Ce cycle doit être un polygone convexe.
- Chaque point qui n'est pas l'un des sommets du polygone doit se trouver à l'extérieur du polygone et doit être relié à l'un des sommets du polygone.
- Il est possible que tous les sommets se trouvent sur le cycle.
Ivan veut peindre un soleil brillant et joli. Il a donc imaginé le score du soleil :
- Définissons $S$ comme l'aire du polygone.
- Définissons $P$ comme la somme des longueurs de tous les segments tracés.
- La valeur $\frac{S}{P}$ est le score du soleil.
Quel est le score maximum possible du soleil ?
Entrée
La première ligne contient un seul entier $t$ ($1 \le t \le 10^4$) — le nombre de cas de test. La description des cas de test suit.
La première ligne de chaque cas de test contient un seul entier $n$ ($3 \le n \le 300$) — le nombre de points.
Chacune des $n$ lignes suivantes contient deux entiers $x_i, y_i$ ($|x_i|, |y_i| \le 10^6$). Tous les points sont distincts. Aucun triplet de points n'est aligné.
Il est garanti que la somme des $n^2$ pour tous les cas de test n'excède pas $90\,000$.
Sortie
Pour chaque cas de test, affichez un seul nombre réel — le score maximum possible du soleil pouvant être tracé.
L'erreur absolue ou relative ne doit pas excéder $10^{-6}$.
Exemples
Entrée 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
Sortie 1
0.3090169943749474 1.2368614277111258 0.2711375415034555 1.5631002094915825
Remarque
L'image du soleil avec le score maximum dans le quatrième cas de test :
Pour ce soleil, $S = 64$, $P = 32 + 4\sqrt{5}$, donc son score est $\frac{64}{32 + 4\sqrt{5}}$.