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.