피뢰침

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

요약

N개의 건물 꼭대기 좌표가 주어질 때, 모든 건물이 피뢰침의 45도 보호 범위 안에 들도록 설치할 최소 건물 수를 구합니다.

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

문제

싱가포르는 연평균 171일에서 186일 사이에 번개가 치는 날이 있다. 싱가포르 땅 1제곱킬로미터에는 1년에 최대 16번 번개가 칠 수 있다. 그래서 싱가포르는 세계적인 번개 다발 국가 중 하나이다.

건축가 Gug는 왼쪽에서 오른쪽으로 $N$ 개의 건물을 살펴본다. 건물 $i$ 꼭대기의 좌표는 $(X_i, Y_i)$ 이다. Gug는 일부 건물 꼭대기에 피뢰침을 설치해서 모든 건물을 보호하려고 한다. 피뢰침은 설치된 건물 자신과, 그 위치에서 왼쪽과 오른쪽으로 45도 아래를 향하는 선 위 또는 아래에 있는 건물을 보호한다. 즉, 건물 $i$ 에 피뢰침을 설치하면 $|X_i - X_j| \le Y_i - Y_j$ 를 만족하는 건물 $j$ 를 보호한다.

모든 건물을 보호하는 데 필요한 피뢰침의 최소 개수를 구한다.

입력

첫 줄에 건물의 수 $N$ 이 주어진다. 이어지는 $N$ 개의 줄에는 각각 정수 $X_i$ 와 $Y_i$ 가 주어진다. $X_i \le X_{i+1}$ 이므로 $X_i$ 는 감소하지 않는다.

입력 크기가 매우 크므로 만점을 받으려면 C++ 빠른 입력을 사용해야 한다.

출력

모든 건물을 보호하는 데 필요한 피뢰침의 최소 개수를 한 줄에 출력한다.

제한

$2 \le N \le 10\,000\,000$

$0 \le X_i, Y_i \le 10^9$

예제3

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