Little Cyan Fish haluaa värittää $n$ pistettä syaanin tai valkoisen väriseksi. $i$-s piste sijaitsee kohdassa $(x_i, y_i)$. Pisteet ovat pareittain erillisiä ja muodostavat aidosti konveksin monikulmion kärkipisteet, lueteltuina vastapäivään.

Olkoon $H_c$ syaanien pisteiden konveksi peite, ja olkoon $H_w$ valkoisten pisteiden konveksi peite. Konveksi peite on pienin konveksi joukko, joka sisältää annetut pisteet. Tyhjän joukon konveksi peite on tyhjä; yhdestä pisteestä tai janasta koostuvan konveksin peitteen pinta-ala on nolla.

Etsi suurin mahdollinen pinta-ala leikkaukselle $H_c \cap H_w$, eli kahden konveksin peitteen yhteiselle alueelle.

Kuva esimerkin kahdesta ensimmäisestä testitapauksesta (ensimmäinen vasemmalla, toinen oikealla).

Syöte

Syötteessä on useita testitapauksia. Syötteen ensimmäinen rivi sisältää yhden kokonaisluvun $T$ ($1 \le T \le 10^4$), joka ilmoittaa testitapausten lukumäärän.

Jokaisen testitapauksen ensimmäinen rivi sisältää yhden kokonaisluvun $n$ ($3 \le n \le 10^5$), joka ilmoittaa pisteiden lukumäärän. Jokainen seuraavista $n$ rivistä sisältää kaksi kokonaislukua $x_i$ ja $y_i$ ($-10^9 \le x_i, y_i \le 10^9$), jotka ilmoittavat $i$-nnen pisteen koordinaatit.

On taattu, että lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $10^5$.

Tuloste

Tulosta jokaiselle testitapaukselle yksi rivi, joka sisältää reaaliluvun: kahden konveksin peitteen leikkauksen suurimman mahdollisen pinta-alan.

Vastauksesi hyväksytään, jos sen absoluuttinen tai suhteellinen virhe on enintään $10^{-8}$. Täsmällisesti sanottuna, olkoon tulosteesi $a$ ja tuomariston vastaus $b$; tulosteesi hyväksytään jos ja vain jos $\frac{|a-b|}{\max(1,|b|)} \le 10^{-8}$.

Esimerkit

Syöte 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

Tuloste 1

5.944444444444444444
0
2.458333333333333404

Huomautus

Esimerkin ensimmäisessä testitapauksessa Little Cyan Fish värittää pisteet $1$, $2$, $4$ ja $6$ syaaneiksi ja muut pisteet valkoisiksi. Syaani nelikulmio ja valkoinen kolmio leikkaavat alueella, jonka pinta-ala on $\frac{107}{18}$, mikä on suurin mahdollinen pinta-ala.

Esimerkin toisessa testitapauksessa ainakin yhdellä värillä on enintään kaksi pistettä, joten leikkauksen pinta-ala on nolla. Kuvassa pisteet $1$, $3$ ja $5$ on väritetty syaaneiksi; valkoinen konveksi peite on pisteet $2$ ja $4$ yhdistävä jana.

Esimerkin kolmannessa testitapauksessa pisteiden $1$, $4$ ja $6$ värittäminen syaaneiksi ja muiden pisteiden värittäminen valkoisiksi antaa suurimman mahdollisen leikkauspinta-alan $\frac{59}{24}$.