First of all, try running O(N^3) solution on sample test case.You will find, that if you calculate redabove and then calculate red_below = red_above, answer wouls come out to 3 as per solution, but when excluded the point lying upon line, answer reduced to 2, which is correct. (Problem statement didn’t clarify that).
From there, i can to know that points may lie on dividkng line.
Suppose we have a line not passing through any red or blue points, and we have calculated answer for this line.
Now, you may try shifting/rotating or both, on this line. You will notice that as long as the line doesnt move over any point, result would remain the same. Got that?.
So this imply we can consider all possible results just by considering lines joining one red point wuth a blue one.
Not sure what you meant to say in the first comment. Why would the exclusion of point lying on the line make the answer any better? It would be the same/worse. Worse case will only happen when 3 points can be colinear. Which can’t happen in this question.
Yeah, I understand that you can transform the line as long it doesn’t cross a point without changing the number of mismatches. This leads to that the line can pass through 2 of the original points(red+blue), but I can’t understand why one of them needs to be red and the other blue.
Thanks…
Glad u liked…