원 예술 작품

시간 제한1초메모리 제한128 MB

요약

최대 100개의 색칠된 점이 주어질 때, 같은 색 두 점을 지나며 다른 색 점을 포함하지 않는 원이 존재하는 색의 개수를 센다.

난이도: 어려움10점 중 8점
유형: 기하, 완전 탐색, 정렬, 구현
정답자: 아직 제출이 없습니다

문제

원은 통일성, 완전함, 무한을 상징하는 오래되고 보편적인 도형입니다. 현대 예술가가 된 우리는 색이 칠해진 점과 원으로 그림을 그리려고 합니다.

먼저 캔버스 위에 여러 개의 색점을 찍습니다. 각 색 $C_i$ 에 대해 다음 두 조건을 모두 만족하는 원을 하나 그리고자 합니다.

그 원의 내부 또는 경계 위에 있는 모든 색점의 색이 $C_i$ 이다.
그 원의 경계 위에 색점이 적어도 두 개 있다.

경계 위의 점도 "내부 또는 경계 위에 있는 점"이므로, 그 색은 반드시 $C_i$ 여야 합니다. 따라서 색 $C_i$ 에 대한 유효한 원은 색이 $C_i$ 인 점을 적어도 두 개 지나며, 다른 색의 점은 내부에도 경계 위에도 하나도 포함하지 않습니다. 색이 $C_i$ 인 점은 원의 내부, 경계, 외부 어디에 있어도 됩니다. 어떤 색에 대해서는 이러한 원이 존재하지 않을 수도 있습니다.

색점들이 주어질 때, 이러한 원이 존재하는 색의 최대 개수(즉, 유효한 원을 하나라도 그릴 수 있는 색의 개수)를 구하세요.

입력

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스의 첫 줄에는 색점의 개수를 나타내는 정수 $n$ ( $1 \le n \le 100$ ) 이 주어집니다. 이어지는 $n$ 개의 줄에는 각각 C X Y 형식으로 한 점의 정보가 주어집니다. 여기서 C 는 그 점의 색(최대 $20$ 개의 영어 소문자로 이루어진 문자열)이고, $X$ , $Y$ 는 정수 좌표로 $-1{,}000{,}000 \le X, Y \le 1{,}000{,}000$ 를 만족합니다.

입력의 마지막 줄에는 $0$ 하나만 주어지며, 이는 입력의 끝을 나타냅니다.

출력

각 테스트 케이스마다, 유효한 원이 존재하는 색의 최대 개수를 한 줄에 출력하세요.

예제5

예제 1

입력

4
red 1 1
blue 1 2
blue 3 2
yellow 3 3
0

예상 출력

예제 2
입력
```
2
green 0 0
green 10 0
0
```
예상 출력
```
1
```

예제 3

입력

4
red 0 0
red 0 2
blue 100 100
blue 100 102
0

예상 출력

예제 4
입력
```
3
a 0 0
a 4 0
b 2 0
0
```
예상 출력
```
0
```
예제 5
입력
```
2
x 0 0
x 5 0
2
y 0 0
z 1 0
0
```
예상 출력
```
1
0
```