Chef and Circle
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
You are given N points on 2-D plane. You have to find out minimal radius of a circle which contains at least M of these points.
First line of the input contains two space separated integer N and M.
Each of the next N lines contains two space separated real numbers denoting the x and y coordinates of i-th point, i.e. xi, yi. These numbers with not contain more than 5 digits after decimal point.
Output a single floating point number corresponding to the minimal radius of a circle with at least M of the above points. Your answer will be considered correct iff its absolute error does not exceed more than 10-2.
- 1 ≤ M ≤ N ≤ 500
- -103 ≤ Xi, Yi ≤ 103
- Subtask #1 (35 points): 1 ≤ N ≤ 200
- Subtask #2 (65 points): 1 ≤ N ≤ 500
Input: 3 3 -1 -1 0 1 1 -1 Output: 1.250000
|Tags||binary-search, geometry, jan17, line-sweep, medium, mgch|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.