Mock CCC '15 S3 - The Tachyon Trap - DMOJ: Modern Online Judge

Mock CCC '15 S3 - The Tachyon Trap

View as PDF

Submit solution

All submissions

Best submissions

Points: 12 (partial)

Time limit: 0.6s

Memory limit: 64M

Authors:

FatalEagle, Alex

Problem types

2015 Mock CCC by Alex and Timothy

The Flash has just met his match at the hands of the Man in the Yellow Suit, a.k.a. the Reverse-Flash, and is chasing him fervently across Central City. Meanwhile, Cisco, Caitlin, and Dr. Wells are drawing up a plan back at S.T.A.R. Labs. They have concluded that Reverse-Flash uses a tachyonic device to corrupt the Speed Force which is responsible for the powers of the Flash and to generate his own negative Speed Force.

Team Flash has a plan to capture Reverse-Flash. They have identified $N$ ~N~ $(3 \le N \le 10)$ ~(3 \le N \le 10)~ two-dimensional points $(x_1, y_1), (x_2, y_2), \dots, (x_N, y_N)$ in Central City where they believe the tachyonic field is weak. These points are numbered from $1$ ~1~ to $N$ ~N~ and the coordinates are all positive integers between $1$ ~1~ and $10\,000$ ~10\,000~. In order to trap Reverse-Flash, Flash will have to run to all $N$ ~N~ points, one after the other in some order, and trace an anti-tachyonic barrier with a special device provided by Dr. Wells. In the end, the Flash's path should join the $N$ ~N~ points and form an $N$ ~N~-sided polygon to trap the Reverse-Flash inside, where his powers are rendered useless. Tachyon fields are very unstable relative to each other, so no three adjacent vertices in the tachyon trap will lie on the same line.

Because the Reverse-Flash is lightning fast and unpredictable, the Flash would like to know of as many ways to create the trap as possible in case Reverse-Flash changes course in their chase. Given the points in Central City where the tachyonic field is weak, S.T.A.R Labs needs your help in determining how many different traps that the Flash can set up to trap the Reverse-Flash.

Input Specification

Line 1 contains an integer $N$ ~N~, the number of points in Central City where the tachyonic field is weak.
The following $N$ ~N~ lines will each contain two space-separated integers $x_i$ ~x_i~ and $y_i$ ~y_i~, representing the vertices of the trap for $i = 1 \dots N$ ~i = 1 \dots N~.