On vous donne $N$ points distincts dans le plan 2D, numérotés de $1$ à $N$. Les coordonnées du point $i$ sont $(x_i, y_i)$.
Chaque point a une couleur. Il y a $N$ couleurs au total, numérotées de $1$ à $N$, et le point $i$ est de couleur $c_i$.
Votre tâche consiste à sélectionner quatre points de couleurs deux à deux distinctes, à les relier dans un ordre quelconque et à former un quadrilatère. Le quadrilatère peut avoir un angle intérieur égal à exactement $180^\circ$, mais aucune paire d'arêtes non adjacentes ne peut s'intersecter.
Déterminez si un tel quadrilatère peut être formé. Si oui, soit $S$ l'aire maximale possible parmi tous les quadrilatères valides, et affichez $2S$ sous la forme d'un entier. S'il ne peut pas être formé, affichez $0$.
Il y a $T$ cas de test indépendants.
Entrée
L'entrée est donnée dans le format suivant :
T case1 case2 : caseT
Ici, chaque $\text{case}_i$ est donné sous la forme suivante :
N x1 y1 c1 x2 y2 c2 : xN yN cN
- Toutes les valeurs d'entrée sont des entiers.
- $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$
- Si $i \neq j$, alors $(x_i, y_i) \neq (x_j, y_j)$.
- La somme totale de $N$ sur l'ensemble des cas de test ne dépasse pas $10^5$.
Sortie
Pour chaque cas de test, affichez la réponse sur sa propre ligne.
Exemples
Exemple d'entrée 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
Exemple de sortie 1
15 17 0 20000000000000000
Note
Dans le premier exemple, relier les points $1, 2, 3, 6$ dans cet ordre forme un quadrilatère valide d'aire $15/2$, ce qui est le maximum parmi tous les choix valides. Le quadrilatère formé par les points $1, 2, 4, 5$ a une aire de $9$, mais les points $1$ et $4$ partagent la même couleur, il est donc invalide.
Dans le deuxième exemple, un quadrilatère valide existe, mais aucun quadrilatère convexe ne satisfait aux exigences.
Dans le troisième exemple, aucun quadrilatère valide ne peut être formé.
Comme le montre le quatrième exemple, la réponse peut être très grande.