사회적 거리 두기 II

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

요약

수직선 위 소들의 위치와 감염 여부가 주어질 때, 감염 반경 R이 정해지지 않은 상황에서 처음에 감염되어 있었을 수 있는 소의 최소 수를 구한다.

난이도: 보통10점 중 5점
유형: 정렬, 그리디, 구현, 배열
정답자: 아직 제출이 없습니다

문제

농부 John은 전염성이 매우 강한 소 질병 COWVID-19가 발생한 뒤 소들의 건강을 걱정하고 있다.

$N$ 마리의 소( $1 \leq N \leq 1000$ )가 "사회적 거리 두기"를 하도록 최선을 다했지만, 안타깝게도 많은 소가 여전히 병에 걸렸다. 편의상 $1 \ldots N$ 번으로 번호가 붙은 소들은 긴 길(사실상 1차원 수직선) 위의 서로 다른 지점에 서 있으며, 소 $i$ 는 위치 $x\_i$ 에 서 있다. 농부 John은 반지름 $R$ 이 있어서, 감염된 소로부터 $R$ 이하만큼 떨어진 곳에 있는 소도 감염되고(그 소는 다시 $R$ 이하만큼 떨어진 다른 소에게 감염을 옮기고, 이런 식으로 계속된다)는 것을 알고 있다.

안타깝게도 농부 John은 $R$ 을 정확히 알지 못한다. 하지만 어느 소가 감염되었는지는 알고 있다. 이 정보가 주어졌을 때, 처음에 감염되어 있었을 수 있는 소의 최소 수를 구하시오.

입력

입력의 첫 줄에는 $N$ 이 주어진다. 다음 $N$ 개의 줄은 각각 한 마리의 소를 두 정수 $x$ 와 $s$ 로 나타내며, $x$ 는 위치( $0 \leq x \leq 10^6$ ), $s$ 는 건강한 소는 0, 병든 소는 1이다. 적어도 한 마리의 소는 병들어 있고, 질병의 확산으로 병들 수 있었던 모든 소는 이제 병들어 있다.

출력

질병이 확산되기 전에 처음에 병들어 있었을 수 있는 소의 최소 수를 출력하시오.

힌트

이 예에서 $R < 3$ 임을 알 수 있다. 그렇지 않으면 위치 7의 소가 위치 10의 소를 감염시켰을 것이기 때문이다. 따라서 적어도 3마리의 소가 처음부터 감염되어 있었어야 한다. 위치 1과 3의 두 소 중 하나, 위치 6과 7의 두 소 중 하나, 그리고 위치 15의 소이다.

예제1

예제 1
입력
```
6
7 1
1 1
15 1
3 1
10 0
6 1
```
예상 출력
```
3
```