Universal Cup Judging System

Universal Cup

時間限制: 4.0 s 記憶體限制: 1024 MB 總分: 100 可 Hack ✓
统计

Du får gitt $N$ forskjellige punkter i 2D-planet, nummerert fra $1$ til $N$. Koordinatene til punkt $i$ er $(x_i, y_i)$.

Hvert punkt har en farge. Det er totalt $N$ farger, nummerert fra $1$ til $N$, og punkt $i$ har farge $c_i$.

Din oppgave er å velge fire punkter med parvis forskjellige farger, forbinde dem i en hvilken som helst rekkefølge og danne en firkant. Firkanten kan ha en indre vinkel på nøyaktig $180^\circ$, men ingen par av ikke-tilstøtende kanter kan krysse hverandre.

Avgjør om en slik firkant kan dannes. Hvis det er mulig, la $S$ være det maksimalt mulige arealet over alle gyldige firkanter, og skriv ut $2S$ som et heltall. Hvis den ikke kan dannes, skriv ut $0$.

Det er $T$ uavhengige testtilfeller.

Inndata

Inndataene er gitt på følgende format:

T
case1
case2
:
caseT

Her er hver $\text{case}_i$ gitt på følgende form:

N
x1 y1 c1
x2 y2 c2
:
xN yN cN
  • Alle inndataverdier er heltall.
  • $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$
  • Hvis $i \neq j$, så er $(x_i, y_i) \neq (x_j, y_j)$.
  • Den totale summen av $N$ over alle testtilfeller overstiger ikke $10^5$.

Utdata

For hvert testtilfelle, skriv ut svaret på en egen linje.

Eksempler

Eksempelinndata 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

Eksempelutdata 1

15
17
0
20000000000000000

Merk

I det første eksempelet danner punktene $1, 2, 3, 6$ forbundet i denne rekkefølgen en gyldig firkant med areal $15/2$, som er det maksimale blant alle gyldige valg. Firkanten dannet av punktene $1, 2, 4, 5$ har areal $9$, men punktene $1$ og $4$ har samme farge, så den er ugyldig.

I det andre eksempelet finnes det en gyldig firkant, men ingen konveks firkant oppfyller kravene.

I det tredje eksempelet kan ingen gyldig firkant dannes.

Som vist i det fjerde eksempelet kan svaret bli svært stort.

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.