TAP2016D - Drawing triangles
[Due to SPOJ restrictions, this problem has been modified with respect to the original version used in the Argentinian Programming Tournament of 2016 in order to have multiple test cases per input file. The original version of this problem (in Spanish) can be found at http://torneoprogramacion.com.ar/wp-content/uploads/2016/09/tap2016.pdf ]
Daniela was offered a Game of Thrones coloring book. Each of the book's pages has N points marked on it, being these points numbered from 1 to N. The challenge is meant to be joining these points with lines in such a way that the figure of a dragon is formed. This problem would be a lot of fun if it was titled "Drawing dragons" and the main character was Daenerys Targaryen, but this is not so. The main character is not
There are multiple test cases in the input file. For each test case, the first line contains an integer number N, representing the number of points marked on the book's page (3 ≤ N ≤ 1000). Each of the following N lines contains two integer numbers, corresponding to one point marked on the page. The integer numbers in the i-th of these lines are Xi and Yi, and they represent the coordinates of the i-th point in a cartesian coordinate system (-100 ≤ Xi, Yi ≤ 100 for i = 1, 2, ..., N). All points given in the input for a test case are distinct, and the first three points always form a triangle.
For each test case, print a single line containing an integer number, representing the number of triangles similar to the one formed by the first three points in the input, which can be formed by joining three of the points marked on the page (counting the triangle formed by the first three points itself).
Input: 6 0 0 1 1 -2 1 5 2 5 0 2 3 3 0 0 1 0 1 1 4 0 0 12 12 3 21 28 -4 4 -100 -100 -100 100 100 -100 100 100 Output: 2 1 3 4
Indeed, maybe it was a little tight. I increased the time limit to 2s now...
Time limit is very strict, my strictly O(n^2) algorithm gets AC in 0.9s.