Universal Cup Judging System

Universal Cup

Limite de temps : 4.0 s Limite de mémoire : 1024 MB Points totaux : 100 Hackable ✓
Statistiques

На двовимірній площині дано $N$ різних точок, пронумерованих від $1$ до $N$. Координати точки $i$ дорівнюють $(x_i, y_i)$.

Кожна точка має певний колір. Усього є $N$ кольорів, пронумерованих від $1$ до $N$, і точка $i$ має колір $c_i$.

Ваше завдання — вибрати чотири точки попарно різних кольорів, з'єднати їх у довільному порядку й утворити чотирикутник. Чотирикутник може мати внутрішній кут, що точно дорівнює $180^\circ$, але жодна пара несуміжних сторін не може перетинатися.

Визначте, чи можна утворити такий чотирикутник. Якщо можна, нехай $S$ — максимально можлива площа серед усіх коректних чотирикутників; виведіть $2S$ як ціле число. Якщо його утворити неможливо, виведіть $0$.

Є $T$ незалежних наборів тестових даних.

Вхідні дані

Вхідні дані подано в такому форматі:

T
case1
case2
:
caseT

Тут кожен $\text{case}_i$ подано в такому вигляді:

N
x1 y1 c1
x2 y2 c2
:
xN yN cN
  • Усі вхідні значення є цілими числами.
  • $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$
  • Якщо $i \neq j$, то $(x_i, y_i) \neq (x_j, y_j)$.
  • Загальна сума $N$ за всіма наборами тестових даних не перевищує $10^5$.

Вихідні дані

Для кожного набору тестових даних виведіть відповідь в окремому рядку.

Приклади

Приклад вводу 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

Приклад виводу 1

15
17
0
20000000000000000

Примітка

У першому прикладі з'єднання точок $1, 2, 3, 6$ у такому порядку утворює коректний чотирикутник площею $15/2$, що є максимумом серед усіх допустимих варіантів. Чотирикутник, утворений точками $1, 2, 4, 5$, має площу $9$, але точки $1$ і $4$ мають однаковий колір, тому він є некоректним.

У другому прикладі коректний чотирикутник існує, проте жоден опуклий чотирикутник не задовольняє вимоги.

У третьому прикладі неможливо утворити жодного коректного чотирикутника.

Як показано в четвертому прикладі, відповідь може бути дуже великою.

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.