Universal Cup Judging System

Universal Cup

Time Limit: 4.0 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

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.

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.