TAP2016D - Drawing triangles

no tags 

[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

Daenerys Stormborn of the House Targaryen
the first of her name
Queen of the Andals, the Rhoynar and the First Men
Lady of the Seven Kingdoms and Protector of the Realm
Khaleesi of the Great Grass Sea
the Unburnt
Breaker of Chains
Mother of Dragons
Queen of Meereen

but it's Daniela, who likes to draw triangles and study their properties. This is definitely a lot more fun than drawing dragons!
Daniela is interested in similar triangles. A triangle is the figure that is formed by joining with line segments three unaligned points. Two triangles are said to be similar if the ratio between their corresponding sides' lengths are always the same. In the figure, triangles ABC and DEF are similar because AB/DE = BC/EF = CA/FD.
Daniela has been looking at one of the books' pages for a while, thinking about the triangle formed by the first three points marked on it. She is wondering how many triangles similar to the one formed by these points can be formed using any three of the N points marked on the page. There are many points so it's going to take a while to find out the answer. She is now very sleepy, but she knows she won't be able to go to bed without knowing it. Can you help her by counting how many triangles similar to the one formed by the first three points (counting this triangle itself) can be formed by joining three points marked on the book's page? This way, she can go to bed and sleep peacefully during the long night.



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).



0 0
1 1
-2 1
5 2
5 0
2 3
0 0
1 0
1 1
0 0
12 12
3 21
28 -4
-100 -100
-100 100
100 -100
100 100


hide comments
Fidel Schaposnik: 2016-09-30 07:40:00

Indeed, maybe it was a little tight. I increased the time limit to 2s now...

[Rampage] Blue.Mary: 2016-09-29 14:13:03

Time limit is very strict, my strictly O(n^2) algorithm gets AC in 0.9s.

Added by:Fidel Schaposnik
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:Argentinian Programming Tournament 2016