USACO 2012 March Contest, Silver Division
Problem 1. Tractor
Contest has ended.
Not submitted
Problem 1: Tractor [Brian Dean, 2012]
After a long day of work, Farmer John completely forgot that he left his
tractor in the middle of the field. His cows, always up to no good, decide
to play a prank of Farmer John: they deposit N bales of hay (1 <= N <=
50,000) at various locations in the field, so that Farmer John cannot
easily remove the tractor without first removing some of the bales of hay.
The location of the tractor, as well as the locations of the N hay bales,
are all points in the 2D plane with integer coordinates in the range
1..1000. There is no hay bale located at the initial position of the
tractor. When Farmer John drives his tractor, he can only move it in
directions that are parallel to the coordinate axes (north, south, east,
and west), and it must move in a sequence of integer amounts. For example,
he might move north by 2 units, then east by 3 units. The tractor cannot
move onto a point occupied by a hay bale.
Please help Farmer John determine the minimum number of hay bales he needs
to remove so that he can free his tractor (that is, so he can drive his
tractor to the origin of the 2D plane).
PROBLEM NAME: tractor
INPUT FORMAT:
* Line 1: Three space-separated integers: N, and the (x,y) starting
location of the tractor.
* Lines 2..1+N: Each line contains the (x,y) coordinates of a bale of
hay.
SAMPLE INPUT (file tractor.in):
7 6 3
6 2
5 2
4 3
2 1
7 3
5 4
6 4
INPUT 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 FORMAT:
* Line 1: The minimum number of bales of hay Farmer John must remove
in order to open up a path for his tractor to move to the
origin.
SAMPLE OUTPUT (file tractor.out):
1
OUTPUT DETAILS:
Farmer John only needs to remove one bale of hay to free his tractor.
Contest has ended. No further submissions allowed.