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

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

트랙터

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

요약
1000×1000 격자에 놓인 최대 50,000개의 건초 더미 중 몇 개를 치워야 트랙터가 축에 평행한 경로로 원점까지 갈 수 있는지 최솟값을 구한다.
난이도

어려움10점 중 8점

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

문제

하루 일과를 마친 농부 John은 밭 한가운데에 트랙터를 두고 온 것을 깜빡했습니다. 짓궂은 소들은 John을 골탕 먹이기로 하고, 밭 곳곳에 건초 더미 NN개(1≤N≤50,0001 \le N \le 50{,}000)를 놓아 두었습니다. 그래서 John은 건초 더미 몇 개를 먼저 치우지 않고서는 트랙터를 쉽게 빼낼 수 없게 되었습니다.

트랙터의 위치와 NN개의 건초 더미 위치는 모두 2차원 평면 위의 점이며, 좌표는 11 이상 10001000 이하의 정수입니다. 트랙터의 처음 위치에는 건초 더미가 없습니다. John이 트랙터를 운전할 때는 좌표축과 평행한 방향(북, 남, 동, 서)으로만 움직일 수 있고, 매번 정수 단위만큼 이동해야 합니다. 예를 들어 북쪽으로 22칸 이동한 뒤 동쪽으로 33칸 이동할 수 있습니다. 트랙터는 건초 더미가 놓인 점으로는 이동할 수 없습니다.

트랙터를 원점 (0,0)(0, 0)까지 운전해 빼내려면 John이 치워야 하는 건초 더미의 최소 개수를 구해 주세요.

입력

  • 첫째 줄: 공백으로 구분된 정수 세 개 — 건초 더미의 개수 NN과 트랙터의 시작 좌표 xx, yy.
  • 둘째 줄부터 NN개의 줄: 각 줄에 건초 더미 하나의 좌표 xx, yy가 주어집니다.

출력

  • 첫째 줄: 트랙터가 원점 (0,0)(0, 0)까지 이동할 수 있도록 John이 치워야 하는 건초 더미의 최소 개수.

예제1

  1. 예제 1

    입력
    7 6 3
    6 2
    5 2
    4 3
    2 1
    7 3
    5 4
    6 4
    예상 출력
    1