Universal Cup Judging System

Universal Cup

时间限制: 4.0 s 内存限制: 1024 MB 总分: 100 可 Hack ✓
统计

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.

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.