All submissions for this problem are available.
Given a set of N integer points on the Cartesian plane. Your task is to find an integer point satisfying its sum of distances to N given points (S) is minimum.
There are several test cases (fifteen at most), each formed as follows:
- The first line contains a positive integer N (N ≤ 2,000).
- N lines follow, each containing a pair of integers (each having an absolute value of 109 at most) describing coordinates of a given point.
The input is ended with N = 0.
For each test case, output on a line a real number (with exactly 6 decimal places) which is the respective minimum sum S found.
Input: 3 1 1 2 2 3 3 5 1 4 2 3 5 2 3 5 4 1 0 Output: 2.828427 9.640986
|Tags||anhdq, april11, easy|
|Time Limit:||2.7551 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, 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, CLOJ, FS|
Fetching successful submissions