Það eru $n$ punktar $p_i$ á tvívíðu plani, þar sem $p_i$ er staðsettur í hnitunum $(x_i, y_i)$. Tryggt er að engir tveir punktar séu á sama stað og engir þrír punktar liggi á sömu línu.

Finndu fjölda leiða til að velja þrjá punkta úr gefna menginu þannig að kúptur hjúpur (convex hull) sérhvers hlutmengis sem inniheldur þessa þrjá punkta sé þríhyrningur.

Inntak

Fyrsta línan inniheldur heiltölu $n$ – fjölda punkta. Hver af næstu $n$ línum inniheldur tvær heiltölur $x_i$ og $y_i$ – hnit punktsins $p_i$.

Úttak

Prentið eina heiltölu – fjölda leiða til að velja þrjá punkta úr gefna menginu þannig að kúptur hjúpur sérhvers hlutmengis sem inniheldur þessa þrjá punkta sé þríhyrningur.

Skorður

$3 \le n \le 2000$, $|x_i|, |y_i| \le 10^9$, engir tveir punktar eru á sama stað, engir þrír punktar liggja á sömu línu.

Dæmi

Inntak 1

7
2 7
0 9
-2 -2
9 4
3 3
-8 -10
-2 -3

Úttak 1

2

Inntak 2

4
-1 -1
1 -1
0 1
0 0

Úttak 2

4

Inntak 3

7
-50 -33
50 -31
-93 98
-47 -59
16 -35
79 -25
-75 41

Úttak 3

15

Skýringar

Gefnu punktarnir í fyrsta dæminu eru staðsettir eins og sýnt er á myndinni hér að neðan.

Í fyrsta dæminu uppfylla eftirfarandi tvær leiðir til að velja þrjá punkta skilyrðið: $\{p_1, p_4, p_6\}$, $\{p_2, p_4, p_6\}$.

Gefnu punktarnir í öðru dæminu eru staðsettir eins og sýnt er á myndinni hér að neðan.

Í öðru dæminu uppfylla eftirfarandi fjórar leiðir til að velja þrjá punkta skilyrðið: $\{p_1, p_2, p_3\}$, $\{p_1, p_2, p_4\}$, $\{p_1, p_3, p_4\}$, $\{p_2, p_3, p_4\}$.