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 (2012-09-17)
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 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.
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.
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.

Input specification

* 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).
* 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).
* 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).

Output specification

* Line 1: The number of different routes FJ can take (this could be zero if there are no valid routes).
;jsessionid=8E2D87ABDA1B7A8BA5FCAF0D236DE53B
* Line 1: The number of different routes FJ can take (this could be zero if there are no valid routes).
;jsessionid=8E2D87ABDA1B7A8BA5FCAF0D236DE53B
* 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

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 1-2-4-3 or 3-4-2-1 before returning to the origin.
;jsessionid=8E2D87ABDA1B7A8BA5FCAF0D236DE53B
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 1-2-4-3 or 3-4-2-1 before returning to the origin.
;jsessionid=8E2D87ABDA1B7A8BA5FCAF0D236DE53B
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 1-2-4-3 or 3-4-2-1 before returning to the origin.
;jsessionid=8E2D87ABDA1B7A8BA5FCAF0D236DE53B

Recommendation

We have carefully selected several similar problems: 1000 | 3675 | 3377 | 1049 | 1494 | 1028