You are not logged in. Please login at www.codechef.com to post your questions!

×

CHEFCIRC - Editorial

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.

    This question is marked "community wiki".

    asked 18 Jan '17, 04:37

    mgch's gravatar image

    6★mgch
    4451436
    accept rate: 20%

    edited 18 Jan '17, 15:01

    admin's gravatar image

    0★admin ♦♦
    19.8k350498541


    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

    link

    answered 19 Jan '17, 19:14

    nishant_coder's gravatar image

    6★nishant_coder
    795
    accept rate: 20%

    edited 19 Jan '17, 19:27

    "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??

    link

    answered 20 Jan '17, 20:22

    kaushal101's gravatar image

    5★kaushal101
    28016
    accept rate: 10%

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

    link

    answered 21 Jan '17, 15:02

    abhisingh10p14's gravatar image

    2★abhisingh10p14
    11
    accept rate: 0%

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

    link

    answered 18 Jan '17, 21:11

    kishu18_agar's gravatar image

    4★kishu18_agar
    21
    accept rate: 0%

    2
    (18 Jan '17, 21:29) mgch6★
    1

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

    (19 Jan '17, 00:09) noob3335★

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

    (19 Jan '17, 09:24) mgch6★

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

    (19 Jan '17, 15:38) kishu18_agar4★

    What is EPS?

    link

    answered 19 Jan '17, 18:58

    vinayak_1's gravatar image

    3★vinayak_1
    191
    accept rate: 0%

    EPS is precision to output - $10^-3$

    (19 Jan '17, 22:10) mgch6★

    "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.

    link

    answered 23 Jan '17, 11:55

    abhisingh10p14's gravatar image

    2★abhisingh10p14
    11
    accept rate: 0%

    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

    link

    answered 25 Jan '17, 01:29

    spinxo's gravatar image

    2★spinxo
    1
    accept rate: 0%

    edited 25 Jan '17, 01:32

    toggle preview
    Preview

    Follow this question

    By Email:

    Once you sign in you will be able to subscribe for any updates here

    By RSS:

    Answers

    Answers and Comments

    Markdown Basics

    • *italic* or _italic_
    • **bold** or __bold__
    • link:[text](http://url.com/ "title")
    • image?![alt text](/path/img.jpg "title")
    • numbered list: 1. Foo 2. Bar
    • to add a line break simply add two spaces to where you would like the new line to be.
    • basic HTML tags are also supported
    • mathemetical formulas in Latex between $ symbol

    Question tags:

    ×15,852
    ×2,657
    ×1,056
    ×647
    ×125
    ×82
    ×4

    question asked: 18 Jan '17, 04:37

    question was seen: 3,531 times

    last updated: 25 Jan '17, 01:32