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

×

# CHEFCIRC - Editorial

Author: Misha Chorniy
Tester: Istvan Nagy
Editorialist: Misha Chorniy

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.

# 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

6★mgch
3451128
accept rate: 23%

0★admin ♦♦
19.7k350498541

 2 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
 2 "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 280●1●6 accept rate: 10%
 1 "there are exactly 2 circles which can be drawn between 2 distinct point" How is that possible? answered 21 Jan '17, 15:02 11 accept rate: 0%
 0 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 21 accept rate: 0% 2 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 (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)
 0 What is EPS? answered 19 Jan '17, 18:58 19●1 accept rate: 0% EPS is precision to output - $10^-3$ (19 Jan '17, 22:10) mgch6★
 0 "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 11 accept rate: 0%
 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 answered 25 Jan '17, 01:29 2★spinxo 1 accept rate: 0%
 toggle preview community wiki:
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,492
×2,559
×1,023
×634
×125
×78
×4

question asked: 18 Jan '17, 04:37

question was seen: 3,450 times

last updated: 25 Jan '17, 01:32