레이팅 미적용긴 하루 일과를 마친 농부 존(Farmer John)은 트랙터를 들판 한가운데에 두고 온 것을 까맣게 잊어버렸다. 언제나 말썽을 꾸미는 소들은 농부 존에게 장난을 치기로 했다. 소들은 들판의 여러 위치에 N개 (1 <= N <= 50,000)의 건초 더미를 가져다 놓아서, 농부 존이 건초 더미를 몇 개 치우지 않고는 트랙터를 쉽게 빼낼 수 없게 만들었다.
트랙터의 위치와 N개의 건초 더미의 위치는 모두 1..1000 범위의 정수 좌표를 가지는 2차원 평면의 점이다. 트랙터의 초기 위치에는 건초 더미가 없다. 농부 존이 트랙터를 몰 때는 좌표축에 평행한 방향(북, 남, 동, 서)으로만 움직일 수 있으며, 정수 단위의 이동을 연속으로 해야 한다. 예를 들어 북쪽으로 2단위 이동한 뒤 동쪽으로 3단위 이동할 수 있다. 트랙터는 건초 더미가 차지한 점 위로 이동할 수 없다.
농부 존이 트랙터를 빼내기 위해(즉, 트랙터를 2차원 평면의 원점까지 몰고 갈 수 있으려면) 치워야 하는 건초 더미의 최소 개수를 구하는 것을 도와주자.
첫째 줄: 공백으로 구분된 세 정수: N과 트랙터의 시작 위치 (x,y).
둘째 줄부터 1+N번째 줄까지: 각 줄에 건초 더미 하나의 (x,y) 좌표가 주어진다.
트랙터가 원점으로 이동할 수 있는 경로를 열기 위해 농부 존이 치워야 하는 건초 더미의 최소 개수.
tractor.in · 출력을 쓸 파일 tractor.out7 6 3
6 2
5 2
4 3
2 1
7 3
5 4
6 41Input details: The tractor starts at (6,3). There are 7 bales of hay, at positions (6,2), (5,2), (4,3), (2,1), (7,3), (5,4), and (6,4).
Output details: Farmer John only needs to remove one bale of hay to free his tractor.