Editorial for Valentine's Day '19 J5 - Falling in Love

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

For the first subtask, we can brute force all pairs of lines.

Time Complexity: \mathcal{O}(N^2)

For the second subtask, we can observe that two lines that have a different slope will always intersect. Two lines that have the same slope and the same y-intercept will also always intersect (along the entirety of the line). Thus, the only pairs we need to find are the ones where the slope is the same and the y-intercept is different. We can use a few hashmaps or maps for this. We can have one hashmap keep track of the number of lines with a certain slope, and another to keep track of the number of lines with a certain slope and a certain y-intercept. Then, we can use inclusion-exclusion to calculate the number of pairs that never intersect.

Time Complexity: \mathcal{O}(N) or \mathcal{O}(N \log N)


There are no comments at the moment.