Little Cyan Fish vill lita $n$ punkta blágræna (cyan) eða hvíta. $i$-ti punkturinn er í $(x_i, y_i)$. Punktarnir eru tveir og tveir ólíkir og eru hornpunktar stranglega kúpts marghyrnings, taldir upp rangsælis.

Látum $H_c$ vera kúpta hjúpinn af blágrænu punktunum, og látum $H_w$ vera kúpta hjúpinn af hvítu punktunum. Kúptur hjúpur er minnsta kúpta mengið sem inniheldur gefnu punktana. Kúptur hjúpur tóms mengis er tómur; kúptur hjúpur sem samanstendur af einum punkti eða striki hefur flatarmálið núll.

Finnið mesta mögulega flatarmál $H_c \cap H_w$, svæðisins sem er sameiginlegt báðum kúptu hjúpunum.

Skýringarmynd af fyrstu tveimur prófunartilvikunum í sýnidæminu (það fyrra til vinstri, það síðara til hægri).

Inntak

Það eru mörg prófunartilvik. Fyrsta línan í inntakinu inniheldur eina heiltölu $T$ ($1 \le T \le 10^4$), sem gefur til kynna fjölda prófunartilvika.

Fyrir hvert prófunartilvik inniheldur fyrsta línan eina heiltölu $n$ ($3 \le n \le 10^5$), sem gefur til kynna fjölda punkta. Hver af næstu $n$ línum inniheldur tvær heiltölur $x_i$ og $y_i$ ($-10^9 \le x_i, y_i \le 10^9$), sem gefa til kynna hnit $i$-ta punktsins.

Það er tryggt að summa $n$ yfir öll prófunartilvik fari ekki yfir $10^5$.

Úttak

Fyrir hvert prófunartilvik skal prenta eina línu sem inniheldur rauntölu, sem gefur til kynna mesta mögulega flatarmál sniðmengis kúptu hjúpanna tveggja.

Svarið þitt verður samþykkt ef algildis- eða hlutfallsleg skekkja þess fer ekki yfir $10^{-8}$. Formlega, látum úttakið þitt vera $a$ og svar dómnefndar vera $b$; úttakið þitt er samþykkt þá og því aðeins að $\frac{|a-b|}{\max(1,|b|)} \le 10^{-8}$.

Dæmi

Inntak 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

Úttak 1

5.944444444444444444
0
2.458333333333333404

Skýring

Í fyrsta prófunartilvikinu í sýnidæminu litar Little Cyan Fish punkta $1$, $2$, $4$ og $6$ blágræna, og hina punktana hvíta. Blágræni ferhyrningurinn og hvíti þríhyrningurinn skarast á svæði með flatarmálið $\frac{107}{18}$, sem er mesta mögulega flatarmálið.

Í öðru prófunartilvikinu í sýnidæminu hefur að minnsta kosti annar liturinn í mesta lagi tvo punkta, þannig að sniðmengið hefur flatarmálið núll. Myndin sýnir punkta $1$, $3$ og $5$ litaða blágræna; hvíti kúpti hjúpurinn er strikið sem tengir punkta $2$ og $4$.

Í þriðja prófunartilvikinu í sýnidæminu gefur það að lita punkta $1$, $4$ og $6$ blágræna og hina punktana hvíta mesta sniðflatarmálið $\frac{59}{24}$.