Little Cyan Fish möchte $n$ Punkte cyan oder weiß färben. Der $i$-te Punkt befindet sich bei $(x_i, y_i)$. Die Punkte sind paarweise verschieden und bilden die Eckpunkte eines streng konvexen Polygons, aufgelistet gegen den Uhrzeigersinn.

Sei $H_c$ die konvexe Hülle der cyanfarbenen Punkte und $H_w$ die konvexe Hülle der weißen Punkte. Eine konvexe Hülle ist die kleinste konvexe Menge, die die gegebenen Punkte enthält. Die konvexe Hülle einer leeren Menge ist leer; eine konvexe Hülle, die aus einem Punkt oder einer Strecke besteht, hat den Flächeninhalt null.

Bestimme den maximal möglichen Flächeninhalt von $H_c \cap H_w$, dem gemeinsamen Bereich der beiden konvexen Hüllen.

Veranschaulichung der ersten beiden Beispieltestfälle (der erste links, der zweite rechts).

Eingabe

Es gibt mehrere Testfälle. Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl $T$ ($1 \le T \le 10^4$), die die Anzahl der Testfälle angibt.

Für jeden Testfall enthält die erste Zeile eine einzelne ganze Zahl $n$ ($3 \le n \le 10^5$), die die Anzahl der Punkte angibt. Jede der folgenden $n$ Zeilen enthält zwei ganze Zahlen $x_i$ und $y_i$ ($-10^9 \le x_i, y_i \le 10^9$), die die Koordinaten des $i$-ten Punktes angeben.

Es wird garantiert, dass die Summe von $n$ über alle Testfälle hinweg $10^5$ nicht überschreitet.

Ausgabe

Gib für jeden Testfall eine einzige Zeile mit einer reellen Zahl aus, die den maximal möglichen Flächeninhalt der Schnittmenge der beiden konvexen Hüllen angibt.

Deine Antwort wird akzeptiert, wenn ihr absoluter oder relativer Fehler $10^{-8}$ nicht überschreitet. Formal: Sei $a$ deine Ausgabe und $b$ die Antwort der Jury; deine Ausgabe wird genau dann akzeptiert, wenn $\frac{|a-b|}{\max(1,|b|)} \le 10^{-8}$ gilt.

Beispiele

Eingabe 1

3
7
0 0
3 0
4 1
3 3
1 4
-1 3
-1 1
5
0 0
2 0
3 1
1 3
-1 1
7
-1000000000 -1000000000
-500000001 -500000002
499999998 499999995
999999998 999999994
500000000 499999997
-499999999 -500000000
-999999999 -999999999

Ausgabe 1

5.944444444444444444
0
2.458333333333333404

Hinweis

Im ersten Beispieltestfall färbt Little Cyan Fish die Punkte $1$, $2$, $4$ und $6$ cyan und die übrigen Punkte weiß. Das cyanfarbene Viereck und das weiße Dreieck überlappen sich in einem Bereich mit dem Flächeninhalt $\frac{107}{18}$, was der maximal mögliche Flächeninhalt ist.

Im zweiten Beispieltestfall hat mindestens eine Farbe höchstens zwei Punkte, sodass die Schnittmenge den Flächeninhalt null hat. Die Abbildung zeigt die Punkte $1$, $3$ und $5$ cyan gefärbt; die weiße konvexe Hülle ist die Verbindungsstrecke der Punkte $2$ und $4$.

Im dritten Beispieltestfall ergibt das Färben der Punkte $1$, $4$ und $6$ in Cyan und der übrigen Punkte in Weiß den maximalen Schnittflächeninhalt von $\frac{59}{24}$.