선 맞춤

NYPC 2017 · 본선

22차원 평면에 xx좌표가 서로 다른 nn개의 점이 주어진다. 이들을 xx좌표 오름차순으로 정렬한 것을 p1p_1, p2p_2, \cdots, pnp_n이라고 하자. 각각의 인접한 두 점 pip_ipi+1p_{i+1}사이를 선분으로 연결하면 모든 점을 지나는 꺾은선(polygonal line) L을 얻을 수 있다. 하지만 꺾은선 LLn1n-1개의 선분으로 이루어진다. 우리는 이 꺾은선 LL의 선분의 개수를 줄이는 대신에 LL이 지나지 않는 점들은 LL로부터 yy축 방향거리가 ϵ\epsilon 이내에 있도록 하고 싶다.

점들의 부분집합 pi1p_{i_1}, pi2p_{i_2}, \cdots, pikp_{i_k} (ij<ij+1i_j < i_{j+1}, knk \le n)를 생각하자. 이 점들에서 인접한 두 점 pijp_{i_j}pij+1p_{i_{j+1}}을 선분으로 연결해서 얻은 꺾은선을 MM이라고 하자. 여기서, pi1=p1p_{i_1}=p_1, pik=pnp_{i_k}=p_n이어야 한다. 다시 말해서, 꺾은선 MM은 첫째 점 p1p_1과 마지막 점 pnp_n은 지나야 한다. 위 부분집합에 속하지 않는 모든 점은 꺾은선 MM으로부터 yy축 방향거리가 ϵ\epsilon이내(거리가 ϵ\epsilon인 경우 포함)에 있어야 한다.

아래 그림은 두 점 pijp_{i_j}pij+1p_{i_{j+1}} 사이의 모든 점이 pijp_{i_j}pij+1p_{i_{j+1}}을 연결하는 선분과 yy축 방향거리가 ϵ\epsilon이내에 있음을 보여준다.

nn개 점의 좌표와 yy축 방향거리 제한 ϵ\epsilon이 주어질 때, 위의 조건을 만족하는 꺾은선 MM을 구성하는 선분 개수 중 최소값을 계산하는 프로그램을 작성하라.

입력 형식

첫째 줄에 점들의 개수를 나타내는 정수 nnyy축 방향거리 제한을 나타내는 정수 ϵ\epsilon이 주어진다. (1n100001 \le n \le 10\,000, 0ϵ10000 \le \epsilon \le 1\,000)

이어지는 nn개의 줄 각각에는 한 점의 좌표 (x,y)(x, y)를 나타내는 두 정수 xxyyxx좌표가 작은 것에서 큰 순서로 주어진다. (106x,y106-10^{6} \le x,y \le 10^{6}) 모든 점의 xx좌표는 서로 다르다.

출력 형식

한 줄에 위의 조건을 만족하는 꺾은선 MM 중에서 선분 개수의 최소값을 출력한다.

예제

입력

4 1 1 2 2 3 3 2 4 -1

출력

2

예제 설명

(1,2)(1, 2), (3,2)(3, 2), (4,1)(4, -1)을 고르면 선분의 개수가 22개로 최소가 된다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

종류 1: 37

n100n \le 100

종류 2: 73

문제의 원래 제한조건 이외의 추가된 제한이 없음.

해설