만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

포로

면접 대비

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

요약
가드 위치가 주어질 때, 서쪽 벽에서 동쪽 벽까지 모든 가드에서 100미터 넘게 떨어진 길이 남도록 제거할 가드의 최소 수를 구합니다.
난이도

보통10점 중 6점

유형
그래프, 기하, BFS
정답자
아직 제출이 없습니다

문제

죄수들이 탈출을 계획하고 있다. 수용소에서 나가는 유일한 길은 길이 PP미터, 너비 LL미터인 협곡을 지난다. 협곡에는 NN명의 보초가 있으며, 각자 자기 자리에 서 있다. 모든 보초의 시야 반경은 정확히 100미터이다. 발각되지 않으려면 협곡을 지나는 동안 가장 가까운 보초까지의 거리가 항상 100미터보다 엄격하게 커야 한다. 아래 그림과 같다.

폭력에 지친 죄수들은 탈출로를 확보하려고 보초를 최소한으로 제거하려 한다. 제거해야 하는 보초의 최소 수를 구하는 프로그램을 작성하라.

죄수들이 어떤 보초든 제거할 수 있다고 가정해도 된다. 다른 보초에게 보이는 보초도 마찬가지다.

입력

첫 줄에 세 정수 PP (1≤P≤500001 \le P \le 50000), LL (1≤L≤500001 \le L \le 50000), NN (1≤N≤2501 \le N \le 250)이 주어진다. 다음 NN개 줄에는 보초 한 명의 정수 좌표 XiX_i, YiY_i가 각각 주어진다 (0≤Xi≤P0 \le X_i \le P, 0≤Yi≤L0 \le Y_i \le L). 협곡의 남서쪽 꼭짓점은 (0,0)(0, 0)이고 북동쪽 꼭짓점은 (P,L)(P, L)이다.

죄수들은 (0,Ys)(0, Y_s) 지점에서 협곡에 들어갈 수 있고 (0≤Ys≤L0 \le Y_s \le L), (P,Yv)(P, Y_v) 지점에서 나갈 수 있다 (0≤Yv≤L0 \le Y_v \le L). 이때 YsY_s와 YvY_v는 정수가 아니어도 된다.

출력

텍스트 파일의 한 줄에 제거해야 하는 보초의 최소 수를 음이 아닌 정수로 출력한다.

예제1

  1. 예제 1

    입력
    530 340 5
    210 50
    330 130
    270 170
    200 180
    260 260
    
    예상 출력
    1