24 hour archive: Problem
1960  Connect the Cows 1960  Connect the Cows 1960  Connect the Cows
Statistics  Sub: 153  AC: 40  AC%: 26,14  Score: 2,78 
Created by  2012 USACO Bronze Division  Brian Dean 
Added by  ymondelo20 (20120917) 
Limits 
Total Time: 20000 MS

Test Time:
2000 MS
Memory: 62 MB  Output: 64 MB  Size:
29 KB

Enabled languages  
Available in 
Description
Every day, Farmer John walks around his farm to check on the health and wellbeing 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 90degree or 180degree 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.
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 90degree or 180degree 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.
Every day, Farmer John walks around his farm to check on the health and wellbeing 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 90degree or 180degree 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.
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 90degree or 180degree 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.
Every day, Farmer John walks around his farm to check on the health and wellbeing 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 90degree or 180degree 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.
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 90degree or 180degree 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.
Input specification
* Line 1: The integer N.
* Lines 2..1+N: Line i+1 contains the x and y coordinates (spaceseparated) of the ith point (each values is in the
* Lines 2..1+N: Line i+1 contains the x and y coordinates (spaceseparated) of the ith point (each values is in the
range 1000...1000).
* Line 1: The integer N.
* Lines 2..1+N: Line i+1 contains the x and y coordinates (spaceseparated) of the ith point (each values is in the
* Lines 2..1+N: Line i+1 contains the x and y coordinates (spaceseparated) of the ith point (each values is in the
range 1000...1000).
* Line 1: The integer N.
* Lines 2..1+N: Line i+1 contains the x and y coordinates (spaceseparated) of the ith point (each values is in the
* Lines 2..1+N: Line i+1 contains the x and y coordinates (spaceseparated) of the ith point (each values is in the
range 1000...1000).
Output specification
* Line 1: The number of different routes FJ can take (this could be
zero if there are no valid routes).
;jsessionid=FD563C2F6164958368AF36019D8D49BC
* Line 1: The number of different routes FJ can take (this could be
zero if there are no valid routes).
;jsessionid=FD563C2F6164958368AF36019D8D49BC
* Line 1: The integer N.
* Lines 2..1+N: Line i+1 contains the x and y coordinates (spaceseparated) of the ith point (each values is in the
* Lines 2..1+N: Line i+1 contains the x and y coordinates (spaceseparated) of the ith point (each values is in the
range 1000...1000).
Sample input
4
0 1
2 1
2 0
2 5
Sample output
2
Hint(s)
There are 4 cows, at positions (0,1), (2,1), (2,0), and (2,5). There are two different routes: Farmer John can visit cows in the orders
1243 or 3421 before returning to the origin.
;jsessionid=FD563C2F6164958368AF36019D8D49BC
There are 4 cows, at positions (0,1), (2,1), (2,0), and (2,5). There are two different routes: Farmer John can visit cows in the orders
1243 or 3421 before returning to the origin.
;jsessionid=FD563C2F6164958368AF36019D8D49BC
There are 4 cows, at positions (0,1), (2,1), (2,0), and (2,5). There are two different routes: Farmer John can visit cows in the orders
1243 or 3421 before returning to the origin.
;jsessionid=FD563C2F6164958368AF36019D8D49BC