2015 Mock CCC by Alex and Timothy

Problem S3: The Tachyon Trap

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 devices to corrupt the Speed Force which is responsible for the powers of the Flash and generate his own negative Speed Force.

Team Flash has a plan to capture Reverse-Flash. They have identified N (3 ≤ N ≤ 10) two-dimensional points (x1, y1), (x2, y2), …, (xN, yN) 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 10000. 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 Format

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

Output Format

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

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

All Submissions
Best Solutions


Point Value: 12 (partial)
Time Limit: 1.00s
Memory Limit: 64M
Added: Feb 18, 2015
Authors: Alex, FatalEagle

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

It's quiet in here...