Universal Cup Judging System

Universal Cup

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

Cho $N$ điểm phân biệt trên mặt phẳng 2D, được đánh số từ $1$ đến $N$. Tọa độ của điểm $i$ là $(x_i, y_i)$.

Mỗi điểm có một màu. Có tất cả $N$ màu, được đánh số từ $1$ đến $N$, và điểm $i$ có màu $c_i$.

Nhiệm vụ của bạn là chọn ra bốn điểm có màu đôi một khác nhau, nối chúng lại theo một thứ tự bất kỳ để tạo thành một tứ giác. Tứ giác này có thể có góc trong bằng đúng $180^\circ$, nhưng không được có cặp cạnh không kề nhau nào cắt nhau.

Hãy xác định xem có thể tạo thành một tứ giác như vậy hay không. Nếu có thể, gọi $S$ là diện tích lớn nhất có thể trong tất cả các tứ giác hợp lệ, và in ra $2S$ dưới dạng một số nguyên. Nếu không thể tạo thành, hãy in ra $0$.

Có $T$ bộ test độc lập.

Dữ liệu vào

Dữ liệu vào được cho dưới định dạng sau:

T
case1
case2
:
caseT

Ở đây, mỗi $\text{case}_i$ được cho dưới dạng sau:

N
x1 y1 c1
x2 y2 c2
:
xN yN cN
  • Tất cả các giá trị đầu vào đều là số nguyên.
  • $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$
  • Nếu $i \neq j$ thì $(x_i, y_i) \neq (x_j, y_j)$.
  • Tổng của $N$ trên tất cả các bộ test không vượt quá $10^5$.

Kết quả

Với mỗi bộ test, in ra câu trả lời trên một dòng riêng.

Ví dụ

Dữ liệu vào mẫu 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

Kết quả mẫu 1

15
17
0
20000000000000000

Ghi chú

Trong ví dụ đầu tiên, nối các điểm $1, 2, 3, 6$ theo thứ tự này sẽ tạo thành một tứ giác hợp lệ có diện tích $15/2$, là giá trị lớn nhất trong tất cả các cách chọn hợp lệ. Tứ giác tạo bởi các điểm $1, 2, 4, 5$ có diện tích bằng $9$, nhưng điểm $1$ và điểm $4$ có cùng màu nên không hợp lệ.

Trong ví dụ thứ hai, tồn tại một tứ giác hợp lệ, nhưng không có tứ giác lồi nào thỏa mãn yêu cầu.

Trong ví dụ thứ ba, không thể tạo thành bất kỳ tứ giác hợp lệ nào.

Như được thấy ở ví dụ thứ tư, kết quả có thể rất lớn.

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.