PREREQUISITES: Binary search, Line equations, slope finding
Okay so here is an editorial for [REDBLUE] using Binary Search. Yes you heard it right. Binary search is enough to solve the 7th problem. Lets start with the naive/brute force solution. Idea is pretty simple. Construct a line using a red and a blue point. The equation will be of form ax+by+c=0. Let us call this f(x,y). As you know given 2 points P1(x1,y1) and P2(x2,y2) you can find if they are in opposite side to the line by satisfying *f(x1,y1)f(x2,y2)<0. If product is >0 then they are on same side. So now we can loop over all red and blue points. Keep 2 counters cnt1=0 and cnt2=0. For a red point if f(x,y)<0 we increment cnt1 else cnt2. For blue point if f(x,y)<0 we increment cnt2 or cnt1. So for this line the minimum points to be deleted is min(cnt1,cnt2). We can do this for all lines that can be drawn for a given pair of red and blue points and find the minimum. Complexity=O(n^3)
[Here] is my brute force code.
Lets try improving this a bit. First fix a blue point. Consider this as the origin of a shifted coordinate system. Now when you draw a line from this blue point to a red point it becomes a line passing through origin in the shifted system. So you can easily see that this line only cuts 2 quadrants whereas 2 other remain unaffected.
As you can see in the figure all the other lines having slopes less than p lie on one side and greater than p lie on other. This can be extended to all quadrants. So what we do is after fixing the blue point we loop over all red points and store their slopes w.r.t the selected blue point for all 4 quadrants. Then we do the same for all blue points except the selected one. Now sort all the slopes in all 4 quadrants. Now choose a red point say r in 1st quadrant. All red points to the right of the line which is formed by joining r with the selected origin(blue point) are:
- all red points in quadrant 2.
- all red points having slope greater than r’s slope in quadrant 1
- all red points having slope less than r’s slope in quadrant 2.
2 and 3 can be found by using binary search in quadrant 1 and 3.
Similarly we can do the same to find all red points to the left of the line and blue points on either side.
This is to be done for all the red points in all quadrants.
So complexity is nnlog(n). n for selecting a blue point and making it origin, then for each blue point choose a red point to form a line with which incurs a cost of n more and finally finding all points on either side of the line take log(n).
Hence complexity becomes: O(n^2*log(n)).
[Here] is my code for 100 points.
If you have any doubts feel free to leave a comment below.