Universal Cup Judging System

Universal Cup

Límite de tiempo: 4.0 s Límite de memoria: 1024 MB Puntuación total: 100 Hackeable ✓
Estadísticas

2차원 평면 위에 서로 다른 $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.