Mock CCC '15 S3 - The Tachyon Trap

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 0.6s
Memory limit: 64M

Authors:
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 (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 to N and the coordinates are all positive integers between 1 and 10\,000. In order to trap Reverse-Flash, Flash will have to run to all 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 points and form an 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, the number of points in Central City where the tachyonic field is weak.
The following N lines will each contain two space-separated integers x_i and y_i, representing the vertices of the trap for i = 1 \dots N.

Output Specification

The output should consist of a single integer — the number of distinct trap shapes that can be made with all N points.

Sample Input

5
1 2
2 2
3 3
2 1
2 5

Sample Output

4

Explanation of Sample

The four ways that Flash can build the tachyon trap is as follows:


Comments


  • 7
    bobhob314  commented on July 31, 2015, 8:29 a.m.

    Can the polygon be self-intersecting?


    • 3
      d  commented on Dec. 31, 2015, 3:49 p.m.

      Looks like the answer is no.