PROBLEM LINK:
Author: Hasan Jaddouh
Tester: Mugurel Ionut Andreica
Editorialist: Kirill Gulin
PROBLEM
You are given N red points and M blue points on a 2D plane. You are required to delete the minimum number of points(the deleted points can be of both colors) so that it’s possible to draw a line such that all remaining red points are on one side of the line while all remaining blue points are on the other side of the line.
QUICK EXPLANATION
For any pair of points draw a straight line connecting them and calculate the minimum number of points need to be deleted on the left and on the right sides of this line for satisfying the problem statement. Use two pointers for fast recalculating how many red and blue points are on some side of the line.
EXPLANATION
It’s obvious that exists a line from the set of lines giving the optimal answer which is close enough to a line built by two points from the input. For proving this take any line which gives the optimal answer and translate it, for example, to the right until you meet any point. After that start rotating the line in any direction around this point until you meet any other point. Easy to see all the points lying at some side of the original line are lying at the same side of the line obtained, so the optimal line can be built by two points from the input.
Subtask 1 solution
Fix any two points from the input and build a line containing them. If these points have coordinates (x_1,y_1) and (x_2, y_2) then you can get line equation in the form of Ax+By+C=0 where A = y_2 - y_1, B = x_1 - x_2, C = -A \cdot x_1 - B \cdot y_1. Now you can determine relative location (lies on the line or on the one of the sides) of any point (x_0, y_0) to this line depending on the sign of the value A \cdot x_0 + B \cdot y_0 + C: all the points lying at the same side have the same sign. So check the location of the remaiming points from the input and calculate how many of them are on the both sides. Suppose there are n_1 red and m_1 blue points at some side and n_2 red and m_2 blue points on the other side. Then update the answer by values n_1 + m_2 and n_2 + m_1. Notice we don’t count fixed points since we can locate them in any side we want by rotating and translating the line by arbitrarily small values.
Time complexity: O((N+M)^3).
Subtask 2 solution
Speed up the solution above. Fix one of the points as one of the points of the line and translate the plane in such a way this point becomes the origin. Sort the remaining points by polar angle relative to the origin. Keep two pointers l r denoting the other point of the line is the l-th point and all the points on the same side of this line form the segment (l, r) of the array of points (remember this array is cyclic). Suppose right now you know the number of red and blue points on the some side. Update the answer and set (l+1)-th point as the second point of the line. Now you need to recalculate the corresponding amounts of points of each colors. The l-th point should be not counted now but several points after the r-th points should be. So increase r until the corresponding point is on the neccessary side.
Time complexity: O((N+M)^2 \log (N+M).
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.