All submissions for this problem are available.
There are N distinct points given - P1,P2,P3,...,PN to be drawn on a 2-dimensional coordinate-system. You draw these points one by one in order. For each point Pi, previous k points, including the point Pi are termed as the point’s ancestors.
k is calculated as follows :
Given K, for a point Pi,
k = i, if i-K<0
Now for each point Pi, proximity is calculated. It is the manhattan distance between the origin and point Q(x,y). Q(x,y) for a point Pi is a point such that the sum of squares of Euclidean distances between Q and each of the ancestors of Pi are minimised. Note that coordinates (x,y) of Q are rounded down to the nearest integers.
Also, for each point, fitness is calculated. It is defined as follows :
Fitness = minx (Number of lines with slope X that pass through all the ancestor points)
In other words, choose a value of X(slope), such that the number of lines of that slope required to pass through all the ancestor points is minimum. Fitness is that minimum number of lines.
The first line consists of the number of points - N, followed by K.
The next N lines each consist of 2 integers - the coordinates of points Pi : Xi and Yi.
For each point, print on a new line, two space separated integers - the Proximity and the Fitness.
1 <= N <= 1000
1 <= K <= 100
0 <= Xi,Yi <= 1000
|Time Limit:||1 - 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.