Little Cyan Fish $n$ нүктені көгілдір (cyan) немесе ақ түске бояғысы келеді. $i$-ші нүкте $(x_i, y_i)$ координатасында орналасқан. Нүктелер қос-қостан әртүрлі және сағат тіліне қарсы ретпен берілген қатаң дөңес көпбұрыштың төбелері болып табылады.

$H_c$ — көгілдір нүктелердің дөңес қабығы, ал $H_w$ — ақ нүктелердің дөңес қабығы болсын. Дөңес қабық дегеніміз — берілген нүктелерді қамтитын ең кіші дөңес жиын. Бос жиынның дөңес қабығы бос болады; бір нүктеден немесе кесіндіден тұратын дөңес қабықтың ауданы нөлге тең.

Екі дөңес қабыққа ортақ аймақ — $H_c \cap H_w$ қиылысуының мүмкін болатын ең үлкен ауданын табыңыз.

Мысалдағы алғашқы екі тест жағдайының иллюстрациясы (біріншісі сол жақта, екіншісі оң жақта).

Кіріс деректер

Бірнеше тест жағдайлары берілген. Кіріс деректердің бірінші жолында тест жағдайларының санын білдіретін бір бүтін сан $T$ ($1 \le T \le 10^4$) берілген.

Әрбір тест жағдайы үшін бірінші жолда нүктелер санын білдіретін бір бүтін сан $n$ ($3 \le n \le 10^5$) берілген. Келесі $n$ жолдың әрқайсысында $i$-ші нүктенің координаталарын білдіретін екі бүтін сан $x_i$ және $y_i$ ($-10^9 \le x_i, y_i \le 10^9$) берілген.

Барлық тест жағдайлары бойынша $n$ мәндерінің қосындысы $10^5$-нен аспайтынына кепілдік беріледі.

Шығыс деректер

Әрбір тест жағдайы үшін бір жолға екі дөңес қабықтың қиылысуының мүмкін болатын ең үлкен ауданын білдіретін бір нақты санды шығарыңыз.

Егер жауабыңыздың абсолюттік немесе салыстырмалы қателігі $10^{-8}$-нен аспаса, ол дұрыс деп қабылданады. Формалды түрде, сіздің шығарған мәніңіз $a$, ал қазылар алқасының жауабы $b$ болсын; сіздің жауабыңыз тек $\frac{|a-b|}{\max(1,|b|)} \le 10^{-8}$ шарты орындалғанда ғана қабылданады.

Мысалдар

Кіріс деректер 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

Шығыс деректер 1

5.944444444444444444
0
2.458333333333333404

Ескертпе

Мысалдағы бірінші тест жағдайында Little Cyan Fish $1$, $2$, $4$ және $6$ нүктелерін көгілдір түске, ал қалған нүктелерді ақ түске бояйды. Көгілдір төртбұрыш пен ақ үшбұрыш ауданы $\frac{107}{18}$ болатын аймақта қиылысады, бұл — мүмкін болатын ең үлкен аудан.

Мысалдағы екінші тест жағдайында кем дегенде бір түсте ең көбі екі нүкте бар, сондықтан қиылысу ауданы нөлге тең. Суретте $1$, $3$ және $5$ нүктелері көгілдір түске боялған жағдай көрсетілген; ақ дөңес қабық $2$ және $4$ нүктелерін қосатын кесінді болып табылады.

Мысалдағы үшінші тест жағдайында $1$, $4$ және $6$ нүктелерін көгілдір түске, ал қалған нүктелерді ақ түске бояу ең үлкен $\frac{59}{24}$ қиылысу ауданын береді.