Editorial for SAC '22 Code Challenge 4 Junior P3 - Obligatory Triangle Problem - Olympiads Online Judge

Editorial for SAC '22 Code Challenge 4 Junior P3 - Obligatory Triangle Problem

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: maxcruickshanks

Subtask 1

It suffices to output $1$ ~1~.

Time Complexity: $\mathcal{O}(1)$ ~\mathcal{O}(1)~

Subtask 2

For each of the $N$ ~N~ points, determine the angle on the unit circle. Trigonometric functions can determine the angle (e.g., atan2 $(y, x)$ ~(y, x)~). Then, normalize the angle to degrees depending on the coding language.

Declare idx to be the index of the point with the closest angle currently to $A$ ~A~ and initially $1$ ~1~.

Next, find the difference between $A$ ~A~ and the current angle.

The angle difference can be determined by $\min(360-abs(a-b), abs(a-b))$ ~\min(360-abs(a-b), abs(a-b))~, where $abs$ ~abs~ returns the absolute value of the parameter and $a$ ~a~ and $b$ ~b~ are angles.

If the difference between $A$ ~A~ and the current angle is smaller than the angle difference between $A$ ~A~ and idx's angle, set idx to the current index.

Finally, output idx.

Time Complexity: $\mathcal{O}(N)$ ~\mathcal{O}(N)~

Comments

There are no comments at the moment.