페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#3907
다국어

조깅 1초 256MB

문제

N명의 학생들이 좌우 폭이 좁은 다리 위에서 조깅을 하고 있다.

각 학생은 모두 다른 위치 A_i에서 출발하여 일정한 속도 B_i로 조깅을 한다.

문제는 다리의 좌우 폭이 좁아 조깅을 하다가 앞의 학생을 추월하는 것이 불가능하기에 부딪힐 정도로 가까워진 경우 속도를 늦춰 앞의 학생과 하나의 그룹이 되어 발을 맞춰 달려야 한다.

그렇게 시간이 충분히 흐른 뒤에 보니 학생들이 여러 그룹을 지어 달리는 모습을 볼 수 있었다.

총 몇 개의 그룹이 존재하게 되는지 출력하는 프로그램을 작성하시오.


입력

첫 줄에 정수 N이 주어진다. (1 \le N \le 100,000)

두 번째 줄부터 i번째 줄에 각 i번째 학생의 시작 위치 A_i와 속도 B_i가 시작 위치의 오름차순으로 주어진다.


출력

시간이 충분히 흐른 뒤 총 몇 개의 그룹이 존재하는지 출력한다.


예제1

입력
5
0 1
1 2
2 3
3 2
6 1
출력
2

예제2

입력
3
0 1
1 4
3 3
출력
2

초기값: 1번 학생: 0에 위치, 2번 학생: 1에 위치, 3번 학생: 3에 위치

잠시후: 1번 학생: 1에 위치, 2번 학생: 5에 위치, 3번 학생: 6에 위치

잠시후: 1번 학생: 2에 위치, 2번 학생: 9에 위치, 3번 학생: 9에 위치

잠시후: 1번 학생: 3에 위치, 2번 학생: 12에 위치, 3번 학생: 12에 위치


태그

출처

USACO 2014 December Bronze

역링크 공식 문제집만