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:
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. :) asked 11 Dec '17, 16:31
showing 5 of 6
show all

A very elegant solution indeed! answered 11 Dec '17, 18:29

Very nice editorial, I was trying something like this method but I couldn't implement it answered 11 Dec '17, 23:04

@gear4 what do you mean radially sweep? please elaborate your solution. answered 12 Dec '17, 01:21

Awesome thinking and implementation indeed!! answered 12 Dec '17, 12:52

@soham1234 why did you not consider line connecting a blue point and a blue point or a line connecting a red with red point ? Also by this approach will minimum answer always be 2 because we are using points to create a line ? in some cases it might be possible that we require to delete only 1 point or none of the points.
Questions says that find a line that requires minimum deletion of points and remaining red points on one side and remaining blue on another. So does that mean we can have 2 points on the line itself ? since 3 or more are not collinear there cannot be more than 2.
Why always 2? It can be zero as well. When I am drawing a line betn 2 points I am not deleting them rather taking them as a reference to choose which side I want the red and the blue point to be on that line and finding all points on other side to that point
And for your first qstn see that a line through red and blue point is enough.You don't need anymore. Proof: Firstly suppose u have taken 2 blue points and drawn a line. Now rotate the line until it touches a red pt. Now no red point crossed this line so cnt of red pt. deletion remains same. In case a blue point did cross the line i.e. went to other side then you can always construct a line betn that blue point and the touching red point. If you find my argument to be faulty you can try finding a case. Anyways even if its wrong you just need a few more cases to modify :)
But we can have 2 points on the line right ? Or the required line(for solution) does not have any red or blue point on it ?
The line won't have points on it. We assume solution line to be very close to the line we form i.e. rotated by a very very small angle A such that no point crosses the line due to this rotation.