Gefnir eru $N$ ólíkir punktar í tvívíða planinu, númeraðir frá $1$ til $N$. Hnit punkts $i$ eru $(x_i, y_i)$.
Hver punktur hefur lit. Alls eru $N$ litir, númeraðir frá $1$ til $N$, og punktur $i$ hefur lit $c_i$.
Verkefni þitt er að velja fjóra punkta með parvísa ólíka liti, tengja þá í hvaða röð sem er og mynda ferhyrning. Ferhyrningurinn má hafa innra horn sem er nákvæmlega $180^\circ$, en engir tveir óaðliggjandi leggir mega skerast.
Ákvarðaðu hvort hægt sé að mynda slíkan ferhyrning. Ef það er hægt, látum $S$ vera stærsta mögulega flatarmál yfir alla gilda ferhyrninga og prentaðu $2S$ sem heiltölu. Ef ekki er hægt að mynda hann skaltu prenta $0$.
Það eru $T$ óháð prófunartilvik.
Inntak
Inntakið er gefið á eftirfarandi sniði:
T case1 case2 : caseT
Hér er hvert $\text{case}_i$ gefið á eftirfarandi formi:
N x1 y1 c1 x2 y2 c2 : xN yN cN
- Öll inntaksgildi eru heiltölur.
- $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$
- Ef $i \neq j$, þá er $(x_i, y_i) \neq (x_j, y_j)$.
- Heildarsumma $N$ yfir öll prófunartilvik fer ekki yfir $10^5$.
Úttak
Fyrir hvert prófunartilvik skaltu prenta svarið á eigin línu.
Dæmi
Dæmi um inntak 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
Dæmi um úttak 1
15 17 0 20000000000000000
Athugasemd
Í fyrsta dæminu myndar tenging punktanna $1, 2, 3, 6$ í þessari röð gildan ferhyrning með flatarmál $15/2$, sem er hámarkið meðal allra gildra valkosta. Ferhyrningurinn sem myndast af punktunum $1, 2, 4, 5$ hefur flatarmálið $9$, en punktarnir $1$ og $4$ hafa sama lit, svo hann er ógildur.
Í öðru dæminu er til gildur ferhyrningur, en enginn kúptur ferhyrningur uppfyllir skilyrðin.
Í þriðja dæminu er ekki hægt að mynda neinn gildan ferhyrning.
Eins og sýnt er í fjórða dæminu getur svarið verið mjög stórt.