Editorial for TLE '17 Contest 7 P1 - Stargazing - Olympiads Online Judge

Editorial for TLE '17 Contest 7 P1 - Stargazing

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: leonchen0613

Use two arrays to keep track of the $X$ $X$ and $Y$ $Y$ coordinates for every planet. Let the first planet be located at the origin $(0, 0)$ $(0, 0)$ . For each other planet, calculate its $X$ $X$ and $Y$ $Y$ coordinates relative to the first planet, using the $X$ $X$ and $Y$ $Y$ coordinates of a previously located planet:

$\displaystyle \begin{align*} x[i] &= x[P_i] + X_i \\ y[i] &= y[P_i] + Y_i \end{align*}$ $\begin{aligned} x [i] & = x [P_{i}] + X_{i} \\ y [i] & = y [P_{i}] + Y_{i} \end{aligned}$

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: $\mathcal O(N \log N)$ $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: $\mathcal O(N^2)$ $O (N^{2})$

Comments

There are no comments at the moment.