All submissions for this problem are available.
In the magic land there is a triangle ABC.
You have N spell cards. Each card has two parameters, i-th card has parameters x[i] and y[i]. Using of the i-th spell card add x[i] to the x-coordinate of the point A and add y[i] to the y-coordinate of the point A. So if A has coordinates (X, Y) it will be moving to (X + x[i], Y + y[i]) by using this card.
You can use at most K spell cards. Applying of several spell cards performs consecutively. So if A was moved to some point A' by the first spell card then second spell card is applied to the new position of A, that is, to the point A', and so on for further cards.
Your task is to find the maximal possible circumference of the triangle ABC after using of at most K spell cards (note that you can use no spell cards). The circumference of a triangle ABC is the sum of its side lengths: |AB| + |BC| + |CA|. And in our problem by triangle we mean any three points A, B, C of the plane. So, in particular, the points A, B, C can lie on the same line, or even some of them can coincide.
The first line of the input contains two integers N and K.
The second line contains two integers Ax and Ay, the coordinates of the point A.
The third line contains two integers Bx and By, the coordinates of the point B.
The fourth line contains two integers Cx and Cy, the coordinates of the point C.
Each of the following N lines contains two integers x[i] and y[i], the parameters of the i-th spell card.
Output should contain a single real number rounded to exactly 13 digits after the decimal point, the maximal possible circumference of the triangle ABC that can be achieved by using at most K spell cards. Your answer will be considered as correct if it has an absolute error less than 10-12.
1 ≤ N ≤ 500
0 ≤ K ≤ N
|Ax|, |Ay|, |Bx|, |By|, |Cx|, |Cy| ≤ 109
|x[i]|, |y[i]| ≤ 106
Input 1: 3 2 0 0 1 0 -1 0 0 1 1 0 1 1 Output 1: 6.8284271247462 Input 2: 3 3 0 0 1 0 -1 0 0 1 1 0 1 1 Output 2: 7.8416192529638
Case 1. Here the optimal way is to use the 1st and the 3rd spell cards. The new coordinates of the point A will be (1, 2). So the circumference of the new triangle ABC is: |(1, 2) − (1, 0)| + |(1, 0) − (-1, 0)| + |(-1, 0) − (1, 2)| = 4 + 2 * sqrt(2).
Case 2. Here the optimal way is to use all of the spell cards. The new coordinates of the point A will be (2, 2). So the circumference of the new triangle ABC is: |(2, 2) − (1, 0)| + |(1, 0) − (-1, 0)| + |(-1, 0) − (2, 2)| = 2 + sqrt(5) + sqrt(13).
|Tags||cgy4ever, hard, oct12|
|Time Limit:||0.37622 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, 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, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.