Problem I/S. 9. (May 2016)
I/S. 9. Buddy discovers \(\displaystyle N\) (\(\displaystyle 1\le N\le 10\)) interesting points in the plane and wants to visit them. Buddy can only move along directions parallel to the coordinate axes, and can only change directions at interesting points (Buddy can even turn back there). Buddy can keep his direction at an interesting point as well. His goal is to visit each interesting point by changing direction at each interesting point exactly once. We say that Buddy inspects an interesting point when he changes direction there. Buddy can pass through an interesting point several times, but wants to investigate it exactly once. He wants to pass through each interesting point and get back to its starting point. We are interested in the number of ways it is possible to inspect all points under these strict restrictions. A closed path and its reversal are considered as two different solutions. Two closed paths are also different if the interesting points have been inspected in a different order. Create a program to count the possible paths. Buddy can start from any point and wants to determine all possibilities.
Your program should read the value of \(\displaystyle N\) from the first line of the standard input, then the integer coordinates of the interesting points (\(\displaystyle -1000\le x, y\le 1000\)) from the next \(\displaystyle N\) lines. The first line of the standard output should contain the number of possible paths.
| Sample input (with newline characters replaced by / characters): | Sample output |
| 4 / 0 1 / 2 1 / 2 0 / 2 -5 | 2 |
Explanation. There are two paths: 1-2-4-3 and 3-4-2-1; Buddy starts from the origin in both cases.
Scoring and bounds. You can get 1 point for a brief and proper documentation clearly describing your solution. Nine further points can be obtained provided that your program solves any valid input within 1 second of running time.
The source code of your program with a short documentation—also describing which developer environment to use for compiling the source—should be submitted in a compressed file is9.zip.
(10 pont)
Deadline expired on June 10, 2016.
Statistics:
10 students sent a solution. 10 points: Gáspár Attila, Gergely Patrik, Janzer Orsolya Lili, Molnár Bálint, Nagy Nándor, Németh 123 Balázs, Noszály Áron, Szakály Marcell. 3 points: 2 students.
Problems in Information Technology of KöMaL, May 2016