CHEFCIRC - Editorial

editorial
, , , , , ,
1

Practice

Contest

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.

    1 Like
    2

    Can someone explain the editorial or some other approach they may have taken for this problem. Editorial is not clear enough.

    3

    After binary search problem was googlable, you can read here: https://www.quora.com/What-is-an-algorithm-for-enclosing-the-maximum-number-of-points-in-a-2-D-plane-with-a-fixed-radius-circle

    2 Likes
    4

    So many papers on that problem but nothing comes close to explaining like that answer.

    1 Like
    5

    Yes, before the contest I had never seen that link, but it was really good explained.

    6

    thanks @mgch, for posting that link. Really good explanation.

    7

    What is EPS?

    8

    I used naive approach with some of the optimizations and my solution passed in 0.27 seconds. Just wanted to know if m solution is very optimized or the solution passed for these test cases only…
    Optimizations were…

    1. Let the current answer be ans. Sort the points and choose two of them… If ans is less than half of the distance between these two points (considering these two points as the end of the diameter of a circle), then there is no need to choose the third point. Else if this circle contains m points, the simply update the ans and there is no need to check for the third point(circle with minimum radius passing through two points will be the circle with these two points as the ends of the diameter of circle).
    2. Choosing two points , there are two circles passing through these two points having radius ans. So check if any of these two circles contains >=m points. If none of these circles contain m points, then no circle with radius<ans can pass through these two points.
    3. Now check for 3 points, if the radius of circle is less than ans ,then only check for the number of points inside this circle and update the ans.

    Is my solution test case dependent or is it actually optimized enough?

    Link to my solution… https://www.codechef.com/viewsolution/12447463

    2 Likes
    9

    EPS is precision to output - 10^-3

    10

    “There are exactly 2 circles which can be drawn between 2 distinct points. There are at most 2∗N2 circles”…could anyone explain how 2 circles can be drawn between 2 distinct points??

    2 Likes
    11

    “there are exactly 2 circles which can be drawn between 2 distinct point” How is that possible?

    1 Like
    12

    “If there exists a circle C that encloses M points, then by slightly moving C it will touch at least two points” , I am unable to visualize this. How it can be so ? Please help in understanding the above given statement.

    13

    The logic of for simple solution have some flaws, if we fix two points and pass a circle through them points inside the circle won’t increase with radius because the circle is covering more area but it is leaving some area in the sector where the original pair of points lies. should check for the test case
    6 4
    -10 0
    10 0
    -3 0
    3 0
    0 -1
    0 1