Annettuna on $N$ erillistä pistettä 2D-tasossa, numeroituina $1$:stä $N$:ään. Pisteen $i$ koordinaatit ovat $(x_i, y_i)$.
Jokaisella pisteellä on väri. Värejä on yhteensä $N$, numeroituina $1$:stä $N$:ään, ja pisteen $i$ väri on $c_i$.
Tehtäväsi on valita neljä pistettä, jotka ovat pareittain erivärisiä, yhdistää ne missä tahansa järjestyksessä ja muodostaa nelikulmio. Nelikulmiossa saa olla täsmälleen $180^\circ$ suuruinen sisäkulma, mutta mitkään kaksi ei-vierekkäistä sivua eivät saa leikata toisiaan.
Selvitä, voidaanko tällaista nelikulmiota muodostaa. Jos voidaan, olkoon $S$ suurin mahdollinen pinta-ala kaikkien kelvollisten nelikulmioiden joukossa, ja tulosta $2S$ kokonaislukuna. Jos sitä ei voida muodostaa, tulosta $0$.
Testitapauksia on $T$ toisistaan riippumatonta.
Syöte
Syöte annetaan seuraavassa muodossa:
T case1 case2 : caseT
Tässä jokainen $\text{case}_i$ annetaan seuraavassa muodossa:
N x1 y1 c1 x2 y2 c2 : xN yN cN
- Kaikki syötteen arvot ovat kokonaislukuja.
- $1 \le T \le 10^4$
- $4 \le N \le 10^5$
- $|x_i|, |y_i| \le 10^8$
- $1 \le c_i \le N$
- Jos $i \neq j$, niin $(x_i, y_i) \neq (x_j, y_j)$.
- Lukujen $N$ kokonaissumma yli kaikkien testitapausten on enintään $10^5$.
Tuloste
Tulosta jokaisen testitapauksen vastaus omalle rivilleen.
Esimerkit
Esimerkkisyöte 1
4 6 2 4 1 5 4 2 6 2 3 5 1 1 2 1 2 1 3 4 4 1 1 1 3 5 2 7 2 3 4 3 4 5 0 0 1 0 1 2 1 0 2 0 2 3 2 0 3 4 0 0 1 0 100000000 2 100000000 0 3 100000000 100000000 4
Esimerkkituloste 1
15 17 0 20000000000000000
Huomautus
Ensimmäisessä esimerkissä pisteiden $1, 2, 3, 6$ yhdistäminen tässä järjestyksessä muodostaa kelvollisen nelikulmion, jonka pinta-ala on $15/2$, mikä on suurin mahdollinen kaikkien kelvollisten valintojen joukossa. Pisteiden $1, 2, 4, 5$ muodostaman nelikulmion pinta-ala on $9$, mutta pisteet $1$ ja $4$ ovat samanvärisiä, joten se ei ole kelvollinen.
Toisessa esimerkissä kelvollinen nelikulmio on olemassa, mutta mikään konveksi nelikulmio ei täytä vaatimuksia.
Kolmannessa esimerkissä ei voida muodostaa yhtään kelvollista nelikulmiota.
Kuten neljännessä esimerkissä nähdään, vastaus voi olla hyvin suuri.