암벽 등반

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

요약

N개의 암벽 지점 중 어떤 K개를 골라도 두 지점 A, B가 있어 미끄러운 정도의 최댓값을 반경으로 하는 위쪽 이동 사슬로 A에서 B까지 갈 수 있을 때, 그러한 최소 K를 구한다.

난이도: 어려움10점 중 8점
유형: 그래프, 그리디, 정렬, DFS
정답자: 아직 제출이 없습니다

문제

어느 화창한 날, Mr. Panda와 Rar the Cat은 암벽 등반을 하기로 했다. 암벽 등반 벽에는 N개의 암석이 있다. i번째 암석은 벽 아래에서 높이 Yi, 벽 중앙에서 오른쪽으로 Xi만큼 떨어진 곳에 있다. Xi가 음수라면 중앙에서 왼쪽에 있다는 뜻이다. 모든 암석의 위치는 서로 다르다.

Mr. Panda의 암벽 등반 실력을 시험하기 위해 Rar the Cat은 그에게 도전 과제를 내기로 했다. 도전 과제는 다음과 같다.

Rar the Cat은 N개의 암석 중 K개의 암석 집합을 고른다. 이 집합을 R이라 한다.
도전에서 이기려면 Mr. Panda는 먼저 집합 R에서 한 쌍의 암석 (A, B)를 골라야 한다. A ≠ B이고 두 암석이 모두 집합 R에 속하기만 하면 어떤 쌍이든 자유롭게 고를 수 있다.
Mr. Panda는 첫 번째 암석 (A)에서 출발해 두 번째 암석 (B)으로 이동하려고 한다. A에서 B로 가는 도중에 다른 암석을 거칠 수 있으며, 그 암석이 집합 R에 속하는지는 상관없다.
하지만 각 암석에는 미끄러움 정도 Si가 있다. 미끄러움 정도가 높은 암석에서는 미끄러지지 않고 멀리 있는 암석으로 뻗기 어렵다. 게다가 Rar the Cat은 위쪽으로만 오르는 것만 허용한다. 더 정확히는, i번째 암석에서 j번째 암석으로 이동하려면 max(|Xi − Xj|, |Yi − Yj|) ≤ max(Si, Sj)이고 Yi < Yj여야 한다.
Mr. Panda는 암석 A에서 암석 B로 이동할 수 있는 한 쌍의 암석 (A, B)를 고르면 도전에서 이긴다. 그렇게 하지 못하면 Mr. Panda는 도전에서 진 것이다.

자세한 내용은 예제 입력과 출력을 참고하라.

물론 Mr. Panda는 도전을 완료할 수 없는 암석 쌍이 많다는 것을 알고 있다. 그는 Rar the Cat이 어떤 암석 집합을 고르더라도 항상 도전을 완료할 수 있게 되는 최소 K를 구하려고 한다. 이 값을 구하는 데 도움을 주자.

입력

프로그램은 표준 입력에서 입력을 읽어야 한다. 입력의 첫 번째 줄에는 정수 N이 하나 주어진다. 다음 N개의 줄에는 정수 3개씩이 주어진다. (i + 1)번째 줄은 i번째 암석의 Xi, Yi, Si를 나타낸다.

출력

프로그램은 Mr. Panda가 항상 도전을 완료할 수 있게 하는 최소 암석 개수를 한 줄에 정수 하나로 표준 출력에 출력해야 한다. Mr. Panda가 도전을 절대 완료할 수 없다면 −1을 출력한다.

예제3

예제 1
입력
```
5
0 3 2
-1 5 1
4 4 3
-1 1 2
2 2 1
```
예상 출력
```
3
```

예제 2

입력

3
0 1 2000000
-1 2 2000000
1 2 2000000

예상 출력

예제 3
입력
```
2
0 1 1
0 5 1
```
예상 출력
```
-1
```