Editorial for TLE '17 Contest 7 P1 - Stargazing
Submitting an official solution before solving the problem yourself is a bannable offence.
Use two arrays to keep track of the ~X~ and ~Y~ coordinates for every planet. Let the first planet be located at the origin ~(0, 0)~. For each other planet, calculate its ~X~ and ~Y~ coordinates relative to the first planet, using the ~X~ and ~Y~ coordinates of a previously located planet:
~x[i] = x[P_i] + X_i~
~y[i] = y[P_i] + Y_i~
After that, there are two main ways to count the number of distinct pairs of coordinates:
Insert all the pairs of coordinates into a set. The size of the set will be your answer. Time Complexity: ~O(N \log N)~
For each planet, loop through all previous planets to check if their coordinates match. If that new planet is unique so far, increment your answer by one. Time Complexity: ~O(N^2)~