트랙터
시간 제한1초메모리 제한128 MB
1000×1000 격자에 놓인 최대 50,000개의 건초 더미 중 몇 개를 치워야 트랙터가 축에 평행한 경로로 원점까지 갈 수 있는지 최솟값을 구한다.
문제
하루 일과를 마친 농부 John은 밭 한가운데에 트랙터를 두고 온 것을 깜빡했습니다. 짓궂은 소들은 John을 골탕 먹이기로 하고, 밭 곳곳에 건초 더미 개()를 놓아 두었습니다. 그래서 John은 건초 더미 몇 개를 먼저 치우지 않고서는 트랙터를 쉽게 빼낼 수 없게 되었습니다.
트랙터의 위치와 개의 건초 더미 위치는 모두 2차원 평면 위의 점이며, 좌표는 이상 이하의 정수입니다. 트랙터의 처음 위치에는 건초 더미가 없습니다. John이 트랙터를 운전할 때는 좌표축과 평행한 방향(북, 남, 동, 서)으로만 움직일 수 있고, 매번 정수 단위만큼 이동해야 합니다. 예를 들어 북쪽으로 칸 이동한 뒤 동쪽으로 칸 이동할 수 있습니다. 트랙터는 건초 더미가 놓인 점으로는 이동할 수 없습니다.
트랙터를 원점 까지 운전해 빼내려면 John이 치워야 하는 건초 더미의 최소 개수를 구해 주세요.
입력
- 첫째 줄: 공백으로 구분된 정수 세 개 — 건초 더미의 개수 과 트랙터의 시작 좌표 , .
- 둘째 줄부터 개의 줄: 각 줄에 건초 더미 하나의 좌표 , 가 주어집니다.
출력
- 첫째 줄: 트랙터가 원점 까지 이동할 수 있도록 John이 치워야 하는 건초 더미의 최소 개수.