Author: Misha Chorniy Difficulty:Medium PreRequisites:sweepline, binary search, polar angle, intersection of 2 circles Problem StatementYou are given $N$ points. Find minimal radius $R$ of the circle, which contains at least $K$ points inside or on the circumference. ExplanationSubtask 1$N$ is less or equal than 200. Welloptimized $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 2For 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.xX_{i}, A.yY_{i})$, and $P_{b}$ for vector $(B.xX_{i}, B.yY_{i})$, possible two cases: If theta lies inside the range $I$ then point $j$, will be inside the circle. Now we can reduce this problem to another wellknown 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 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

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... Is my solution test case dependent or is it actually optimized enough? Link to my solution.. https://www.codechef.com/viewsolution/12447463 answered 19 Jan '17, 19:14

"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?? answered 20 Jan '17, 20:22

"there are exactly 2 circles which can be drawn between 2 distinct point" How is that possible? answered 21 Jan '17, 15:02

Can someone explain the editorial or some other approach they may have taken for this problem. Editorial is not clear enough. answered 18 Jan '17, 21:11
2
After binary search problem was googlable, you can read here: https://www.quora.com/Whatisanalgorithmforenclosingthemaximumnumberofpointsina2Dplanewithafixedradiuscircle
(18 Jan '17, 21:29)
1
So many papers on that problem but nothing comes close to explaining like that answer.
(19 Jan '17, 00:09)
Yes, before the contest I had never seen that link, but it was really good explained.
(19 Jan '17, 09:24)
thanks @mgch, for posting that link. Really good explanation.
(19 Jan '17, 15:38)

What is EPS? answered 19 Jan '17, 18:58

"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. answered 23 Jan '17, 11:55

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 answered 25 Jan '17, 01:29
