Universal Cup Judging System

Universal Cup

Limite de temps : 4.0 s Limite de mémoire : 1024 MB Points totaux : 100 Hackable ✓
Statistiques

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.

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.