아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

보석 레이스

시간 제한2초메모리 제한256 MB

요약
옆 방향 속도가 제한된 채로 아래에서 위로 달리면서 주울 수 있는 보석의 최대 개수를 구합니다.
난이도

보통10점 중 7점

유형
동적 계획법, 정렬, 이분 탐색
정답자
아직 제출이 없습니다

문제

레이싱 게임을 한다. 캐릭터는 xx축(y=0y = 0) 위에서 출발해 트랙을 따라 위로 달린다. 트랙의 좌우 경계는 직선 x=0x = 0과 직선 x=wx = w이다. 출발 지점의 가로 좌표는 트랙 안이기만 하면 원하는 대로 고를 수 있다. 결승선은 y=hy = h이고, 이 선에 닿으면 게임이 끝난다.

세로 속도는 vv로 고정되어 있다. 반면 가로 속도는 −v/r-v/r 이상 v/rv/r 이하의 값 중 아무 값이나 고를 수 있고, 언제든지 바꿀 수 있다.

트랙 위 정해진 nn개의 지점에 보석이 하나씩 놓여 있다. 보석을 최대한 많이 모으려고 한다. 한 번의 주행에서 모을 수 있는 보석은 최대 몇 개인가?

입력

첫째 줄에 네 정수 nn, rr, ww, hh가 공백으로 구분되어 주어진다 (1≤n≤1051 \le n \le 10^5, 1≤r≤101 \le r \le 10, 1≤w,h≤1091 \le w, h \le 10^9).

다음 nn개의 줄에는 각각 두 정수 xix_i와 yiy_i가 공백으로 구분되어 주어진다. 이는 ii번째 보석의 좌표이다 (0≤xi≤w0 \le x_i \le w, 0<yi≤h0 < y_i \le h). 한 위치에 보석이 둘 이상 놓이는 경우는 없다.

vv의 값은 입력에 주어지지 않는다.

출력

주행 중 모을 수 있는 보석의 최대 개수를 한 줄에 출력한다.

예제3

  1. 예제 1

    입력
    5 1 10 10
    8 8
    5 1
    4 6
    4 7
    7 9
    
    예상 출력
    3
    
  2. 예제 2

    입력
    5 1 100 100
    27 75
    79 77
    40 93
    62 41
    52 45
    
    예상 출력
    3
    
  3. 예제 3

    입력
    10 3 30 30
    14 9
    2 20
    3 23
    15 19
    13 5
    17 24
    6 16
    21 5
    14 10
    3 6
    
    예상 출력
    4