Author: Misha Chorniy
Tester: Istvan Nagy
Editorialist: Misha Chorniy
Difficulty:
Medium
Pre-Requisites:
sweepline, binary search, polar angle, intersection of 2 circles
Problem Statement
You are given N points. Find minimal radius R of the circle, which contains at least K points inside or on the circumference.
Explanation
Subtask 1
N is less or equal than 200. Well-optimized O(N^4) can pass and O(N^3 log (max(|X|,|Y|)/EPS)) too.
Describe O(N^4) solution below.
Will call circle interesting if it contains at least one point from the N points, and if we move this circle in any direction this circle will contain another set of points. Which circles are interesting? That circles which are constructed from 3 points(if they donât lie on the same line), or from 2 points(if segment which connects they are the diameter of the circle). We need to go over all interesting circles and check the number of points which lies inside of them.
Letâs use next observation, if there are at least K points lies inside a circle of the radius R, then at least K points lies inside any circle with a radius bigger than R. Also if K points donât lie inside the circle of R, then K doesnât lie inside any circle with a radius smaller than R. The function of a radius is monotonic, we can use binary search for solving this problem. Rephrase problem, we have radius R, find a maximal number of points which lies inside of a circle with radius R and compare it with K.
Use this observation for solving problem in O(N^3 log (max(|X|, |Y|)/EPS))
Will iterate over a pair of points i and j, if the distance between them more than EPS, will try to carry out through them the circles(this points will lie on the circumference), there are exactly 2 circles which can be drawn between 2 distinct points. There are at most 2*N^2 circles, and after building circles, iterate over all points and check if they lie inside of the circles in O(1), hence O(N^3) complexity for checking with radius R.
Subtask 2
For this subtask use scanline approach and binary search by radius. The first step is binary search by radius, secondly iterate over point i with coordinates (X,Y) which will lie on the circumference of the circle, then the center of the circle lies somewhere with coordinates (X+R*cos(theta), Y+R*sin(theta)). For every point j != i find all possible angles theta which satisfied condition that point j lies inside of circle of radius R and centered in point (X+R*cos(theta), Y+R*sin(theta)).
Let we have point i and j (i != j), how to find all thetaâs described above? At first, if \sqrt((X_{i}-X_{j})^2+(Y_{i}-Y_{j})^2) (Euclidian distance between point i and j) more than 2*R, there are no thetaâs satisfied condition. In another case, letâs say that we have two circles of radius R centered in points i and j. Find points where they intersect, in every point of their intersection, can be placed a circle of the radius R, and it will contain both points i and j. All thetaâs which satisfied condition lie within some sector of the circle centered in point i and with the radius R.
Letâs find intersection between two circles centered in points i and j with radiuses R. Call these points as A and B(in case if circles intersect in one point, assume that B = A). Let P_{a} will be polar angle for vector (A.x-X_{i}, A.y-Y_{i}), and P_{b} for vector (B.x-X_{i}, B.y-Y_{i}), possible two cases:
- P_{a} <= P_{b}, then theta can lie in the range I = [P_{a}; P_{b}]
- P_{a} > P_{b}, then theta can lie in the range I = [P_{a}; 2*PI) U [0; P_{b}]
If theta lies inside the range I then point j, will be inside the circle. Now we can reduce this problem to another well-known problem, there are segments, we need to find the point which covered with the maximal number of segments. It can be solved with standard sweep line technique.
The overall time complexity of this approach is O(N^2 * log N * log (max(|X|,|Y|)/EPS)).
Solution:
Setterâs solution can be found here
Testerâs solution can be found here
Please feel free to post comments if anything is not clear to you.