Universal Cup Judging System

Universal Cup

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

Gegeben sind $N$ verschiedene Punkte in der 2D-Ebene, nummeriert von $1$ bis $N$. Die Koordinaten von Punkt $i$ sind $(x_i, y_i)$.

Jeder Punkt hat eine Farbe. Es gibt insgesamt $N$ Farben, nummeriert von $1$ bis $N$, und Punkt $i$ hat die Farbe $c_i$.

Deine Aufgabe ist es, vier Punkte mit paarweise verschiedenen Farben auszuwählen, sie in beliebiger Reihenfolge zu verbinden und so ein Viereck zu bilden. Das Viereck darf einen Innenwinkel von genau $180^\circ$ besitzen, aber kein Paar nicht benachbarter Kanten darf sich schneiden.

Bestimme, ob ein solches Viereck gebildet werden kann. Falls ja, sei $S$ der größtmögliche Flächeninhalt über alle gültigen Vierecke, und gib $2S$ als ganze Zahl aus. Falls keines gebildet werden kann, gib $0$ aus.

Es gibt $T$ unabhängige Testfälle.

Eingabe

Die Eingabe erfolgt im folgenden Format:

T
case1
case2
:
caseT

Hierbei ist jedes $\text{case}_i$ in der folgenden Form gegeben:

N
x1 y1 c1
x2 y2 c2
:
xN yN cN
  • Alle Eingabewerte sind ganze Zahlen.
  • $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$
  • Wenn $i \neq j$ ist, dann gilt $(x_i, y_i) \neq (x_j, y_j)$.
  • Die Gesamtsumme von $N$ über alle Testfälle hinweg überschreitet $10^5$ nicht.

Ausgabe

Gib für jeden Testfall die Antwort in einer eigenen Zeile aus.

Beispiele

Beispieleingabe 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

Beispielausgabe 1

15
17
0
20000000000000000

Hinweis

Im ersten Beispiel bildet das Verbinden der Punkte $1, 2, 3, 6$ in dieser Reihenfolge ein gültiges Viereck mit dem Flächeninhalt $15/2$, was das Maximum unter allen gültigen Auswahlmöglichkeiten ist. Das durch die Punkte $1, 2, 4, 5$ gebildete Viereck hat den Flächeninhalt $9$, aber die Punkte $1$ und $4$ haben dieselbe Farbe, weshalb es ungültig ist.

Im zweiten Beispiel existiert zwar ein gültiges Viereck, aber kein konvexes Viereck erfüllt die Anforderungen.

Im dritten Beispiel kann kein gültiges Viereck gebildet werden.

Wie im vierten Beispiel gezeigt, kann die Antwort sehr groß werden.

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.