USACO 2012 March Contest, Bronze Division
Problem 2. Connect the Cows
Contest has ended.
Not submitted
Problem 2: Connect the Cows [Brian Dean, 2012]
Every day, Farmer John walks around his farm to check on the health and
well-being of his N (1 <= N <= 10) cows.
The location of each cow is described by a point in the 2D plane, and
Farmer John starts out at the origin (0,0). To make his route more
interesting, Farmer John decides that he will only walk in directions
parallel to the coordinate axes -- that is, only north, south, east, or
west. Furthermore, he only changes his direction of travel when he reaches
the location of a cow (he may also opt to pass through the location of a
cow without changing direction, if desired). When he changes his direction
of travel, he may make either a 90-degree or 180-degree turn. FJ's route
must take him back to the origin after visiting all his cows.
Please compute the number of different routes FJ can take to visit his N
cows, if he changes direction exactly once at the location of each cow. He
is allowed to pass through the location of a cow without changing direction
an arbitrary number of times. The same geometric route taken forward
versus backward counts as two different routes.
PROBLEM NAME: connect
INPUT FORMAT:
* Line 1: The integer N.
* Lines 2..1+N: Line i+1 contains the x and y coordinates
(space-separated) of the ith point (each values is in the
range -1000...1000).
SAMPLE INPUT (file connect.in):
4
0 1
2 1
2 0
2 -5
INPUT DETAILS:
There are 4 cows, at positions (0,1), (2,1), (2,0), and (2,-5).
OUTPUT FORMAT:
* Line 1: The number of different routes FJ can take (this could be
zero if there are no valid routes).
SAMPLE OUTPUT (file connect.out):
2
OUTPUT DETAILS:
There are two different routes: Farmer John can visit cows in the orders
1-2-4-3 or 3-4-2-1 before returning to the origin.
Contest has ended. No further submissions allowed.