#P2988. Function Approximation

Function Approximation

Description

For a sequence of real ordered pairs { <x0, y0>, <x1, y1>, …, <xn, yn> } satisfying x0 < x1 < … < xn and any sequence of integers satisfying 0 = i0 < i1 < … < im = n, define

We wish to find the minimum possible value of .

Input

The input begins with the integers n and m (0 < mn ≤ 100), which are followed by the ordered pairs <xi, yi> (|xi|, |yi| ≤ 104, 0 ≤ in).

Output

The output contains only the minimum possible value of Δ. Any answers with a absolute error within 10−7 or a relative error within 10−9 are accepted.

1 1
0 0
1 1
0

Hint

sgn(x) is the sign function of x, which evaluates to for any non-zero x and 0 otherwise.

Source

POJ Monthly--2006.08.27, frkstyc