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.