Se te dan $N$ puntos distintos en el plano 2D, numerados del $1$ al $N$. Las coordenadas del punto $i$ son $(x_i, y_i)$.
Cada punto tiene un color. Hay $N$ colores en total, numerados del $1$ al $N$, y el punto $i$ tiene el color $c_i$.
Tu tarea consiste en seleccionar cuatro puntos con colores distintos dos a dos, conectarlos en cualquier orden y formar un cuadrilátero. El cuadrilátero puede tener un ángulo interior de exactamente $180^\circ$, pero ningún par de lados no adyacentes puede intersectarse.
Determina si se puede formar dicho cuadrilátero. Si es posible, sea $S$ el área máxima posible entre todos los cuadriláteros válidos, e imprime $2S$ como un número entero. Si no se puede formar, imprime $0$.
Hay $T$ casos de prueba independientes.
Entrada
La entrada se proporciona en el siguiente formato:
T case1 case2 : caseT
Aquí, cada $\text{case}_i$ se da de la siguiente forma:
N x1 y1 c1 x2 y2 c2 : xN yN cN
- Todos los valores de entrada son enteros.
- $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$, entonces $(x_i, y_i) \neq (x_j, y_j)$.
- La suma total de $N$ en todos los casos de prueba no supera $10^5$.
Salida
Para cada caso de prueba, imprime la respuesta en su propia línea.
Ejemplos
Entrada de ejemplo 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
Salida de ejemplo 1
15 17 0 20000000000000000
Nota
En el primer ejemplo, conectar los puntos $1, 2, 3, 6$ en este orden forma un cuadrilátero válido con área $15/2$, que es el máximo entre todas las elecciones válidas. El cuadrilátero formado por los puntos $1, 2, 4, 5$ tiene área $9$, pero los puntos $1$ y $4$ comparten el mismo color, por lo que no es válido.
En el segundo ejemplo, existe un cuadrilátero válido, pero ningún cuadrilátero convexo cumple los requisitos.
En el tercer ejemplo, no se puede formar ningún cuadrilátero válido.
Como se muestra en el cuarto ejemplo, la respuesta puede ser muy grande.