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)$ $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 - a b s (a - b), a b s (a - b))$ , where $abs$ $a b s$ 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)$ $O (N)$

Comments

There are no comments at the moment.