Mock CCC '19 Contest 2 S3 - Tudor Tallies Triangular Totals

View as PDF

Submit solution


Points: 10 (partial)
Time limit: 7.0s
Memory limit: 1G

Problem type

Tudor has decided to build a triangular pen for his goats!

Tudor has identified N locations on his farm where he can install fence posts. To construct a pen, Tudor will install fence posts at exactly three locations, and then build fences between those fence posts.

For obvious reasons, Tudor must select fence posts such that there is strictly positive area for the goats to roam around inside.

How many different pens can Tudor construct? Two pens are different if a fence post is installed in one but not in the other.

Constraints

4 \le N \le 3000

In tests worth 5 marks, N \le 10

-10^{18} \le x_i, y_i \le 10^{18}

All fence post candidate locations will be pairwise distinct.

Input Specification

The first line of the input is a single positive integer N.

N lines follow, each containing two space-separated integers x_i and y_i, indicating that a fence post can be installed at (x_i, y_i).

Output Specification

Output, on a single line, the number of distinct triangular pens Tudor can build.

Sample Input

4
0 0
1 0
2 0
1 1

Sample Output

3

Comments


  • 0
    rickywen12345  commented on Feb. 19, 2019, 8:15 p.m. edited

    what does the question mean by "positive space"? How do u generate a triangle with negative space. For the sample test case Im counting 4 triangles. Can someone explain this to me please. Thanks

    Edit: Nvm, realized that 0,0 1,0 and 2,0 make a straight line so it's not a triangle.