Universal Cup Judging System

Universal Cup

시간 제한: 4.0 s 메모리 제한: 1024 MB 총점: 100 해킹 가능 ✓
통계

Du får $N$ skilda punkter i 2D-planet, numrerade $1$ till $N$. Koordinaterna för punkt $i$ är $(x_i, y_i)$.

Varje punkt har en färg. Det finns totalt $N$ färger, numrerade $1$ till $N$, och punkt $i$ har färgen $c_i$.

Din uppgift är att välja fyra punkter med parvis skilda färger, förbinda dem i valfri ordning och bilda en fyrhörning. Fyrhörningen får ha en innervinkel på exakt $180^\circ$, men inget par av icke-intilliggande kanter får skära varandra.

Avgör om en sådan fyrhörning kan bildas. Om det går, låt $S$ vara den maximalt möjliga arean över alla giltiga fyrhörningar, och skriv ut $2S$ som ett heltal. Om det inte går, skriv ut $0$.

Det finns $T$ oberoende testfall.

Indata

Indatan ges i följande format:

T
case1
case2
:
caseT

Här ges varje $\text{case}_i$ på följande form:

N
x1 y1 c1
x2 y2 c2
:
xN yN cN
  • Alla indatavärden är heltal.
  • $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$
  • Om $i \neq j$, så är $(x_i, y_i) \neq (x_j, y_j)$.
  • Den totala summan av $N$ över alla testfall överstiger inte $10^5$.

Utdata

För varje testfall, skriv ut svaret på en egen rad.

Exempel

Exempelindata 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

Exempelutdata 1

15
17
0
20000000000000000

Förklaring

I det första exemplet bildar punkterna $1, 2, 3, 6$ förbundna i denna ordning en giltig fyrhörning med area $15/2$, vilket är det maximala bland alla giltiga val. Fyrhörningen som bildas av punkterna $1, 2, 4, 5$ har area $9$, men punkterna $1$ och $4$ har samma färg, så den är ogiltig.

I det andra exemplet finns en giltig fyrhörning, men ingen konvex fyrhörning uppfyller kraven.

I det tredje exemplet kan ingen giltig fyrhörning bildas.

Som visas i det fjärde exemplet kan svaret bli mycket 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.