Editorial for VMSS '15 #3 - Jeffrey and Roads

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

Note that since the roads extend forever, it is impossible for Jeffrey to go "around" the lines to the school. Thus Jeffrey has to cross a road if and only if he and the school are on different sides of the road.

Now how do we check if they're on different sides? Notice that the equation for the roads are conveniently given to use in $AX + BY + C = 0$ ~AX + BY + C = 0~ form. If you remember from math class, having $AX + BY + C = 0$ ~AX + BY + C = 0~ with coordinates $(X, Y)$ ~(X, Y)~ means that you are ON the line. (thankfully, the question guarantees that does not happen) Now what happens if $AX + BY + C < 0$ ~AX + BY + C < 0~? It means that the coordinate $(X, Y)$ ~(X, Y)~ is on 1 side of the line. But what happens if $AX + BY + C > 0$ ~AX + BY + C > 0~? It means that the coordinate $(X, Y)$ ~(X, Y)~ is on the other side of the line. In fact, you can try it out on the Desmos calculator online to see for yourself.

Now with that info in mind, we can see Jeffrey and the school are on different sides of the road if one is negative and the other is positive.

Final Complexity: $\mathcal O(N)$ ~\mathcal O(N)~

Comments

There are no comments at the moment.