Submit Best Submissions All Submissions

384. Counting Triangles

Problem Statement:
Triangle Tom is at it again. This time, however, instead of attempting to calculate areas of triangles, he just wants to count how many of them there are. Given a list of possible points, your job will be to help Tom figure out how many different triangles can be formed with those points.

The Problem:
Given a list of points in the Cartesian plane, determine how many triangles (with all angles strictly less than 180º) can be formed with those points.

Input Format:
The first line of the file will contain a single positive integer n (1 <= n <= 50), denoting the number of test cases in the file. The first line of each test case contains one integer, k (1 <= k <= 100), denoting the number of points for that test case.
The second line of each test case contains k ordered pairs of integers (separated by spaces) denoting the x and y coordinates of each point, respectively. It is guaranteed that -100 <= x <= 100 and -100 <= y <= 100 for all coordinates. It is also guaranteed that each point given will be unique.

Output Format:
At the beginning of each test case, output "Test case #t: ", where t is the test case number (starting from 1). Follow this with a statement of the following form:

x triangle(s) can be formed.

where x represents the distinct number of triangles that can be formed with the given points. Leave a blank line after the output for each data set.

Follow the format illustrated in Sample

Sample Input:
2 4 1 1 2 2 3 4 4 4 3 2 4 6 8 7 9

Sample Output:
Test case #1: 3 triangle(s) can be formed. Test case #2: 0 triangle(s) can be formed.

Added by: muaz.32
Added at: 2015-03-13 13:00:00 UTC
Time Limit: 3 seconds
Partial score: No
Source:DCPC training 2015