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.

Time Complexity: \mathcal{O}(1)

Subtask 2

For each of the N points, determine the angle on the unit circle. Trigonometric functions can determine the angle (e.g., atan2(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 and initially 1.

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

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

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

Finally, output idx.

Time Complexity: \mathcal{O}(N)


Comments

There are no comments at the moment.