### Problem Statement

We want to find the location of a local maximum in an unknown function. y = f(x) is a continuous real-valued function defined on the real numbers. We already have a number of data pairs, (xi, yi), and we need to find a small interval on the x axis that is guaranteed to contain at least one local (or global) maximum. But taking a sample from this function is quite expensive so we are only allowed to take N samples. Our problem is to choose them in such a way as to minimize the size of the interval that we determine.

The sampling will be done sequentially: we choose a value of x and find the corresponding y value, f(x). We repeat this process N times, choosing the x value based on all the data collected so far. We are willing to assume that no two y values will be exactly equal to each other.

Create a class LocalMax that contains a method length that is given N, the number of samples we can take, and double[]s xData and yData (the existing data pairs). It will return the worst case length for our interval around a local maximum using optimal sampling. If it is not possible to make such a guarantee, it returns -1.0.

### Definition

 Class: LocalMax Method: length Parameters: int, double[], double[] Returns: double Method signature: double length(int N, double[] xData, double[] yData) (be sure your method is public)

### Notes

-The returned value must be accurate to within a relative or absolute value of 1E-9

### Constraints

-N will be between 0 and 25 inclusive.
-xData will contain between 1 and 50 elements inclulsive.
-yData will contain the same number of elements as xData.
-The elements of yData will be distinct.
-The elements of xData will be distinct.
-Each element of xData and yData will be greater than 0.0 and less than 10000.0.

### Examples

0)

 `1` `{3,4,5}` `{3,4,5}`
`Returns: -1.0`
 From the data we already have we cannot guarantee that this function even has a local maximum -- it might be monotonically increasing.
1)

 `0` `{3,4,5}` `{3,5,4} `
`Returns: 2.0`
 We know that there is a local maximum between x=3 and x=5.
2)

 `2` `{3,5,8}` `{35,923.2,17} `
`Returns: 2.0`
 Here is one way (there are others) get an interval of length 2 or less with just two additional samples. Take the first sample at x=6.5. The worst case is that the corresponding y value is less than 923.2. In that case we know that the interval (3,6.5) contains a local maximum, and that the y value at x=5 is greater than either endpoint y value. Take the second sample at x=4.7. In the worst case the corresponding value of y will be bigger than 923.2, in which case we could conclude that there is a local max somewhere in the interval (3,5).
3)

 `1` `{3,4,6,5}` `{32,53,68,47}`
`Returns: 1.0`
 If we take a sample at x=4.0+epsilon, for some tiny epsilon, then the worst case would be that the corresponding y value would be smaller than 53. In that case the interval between 3.0 and 4.0+epsilon would contain a local maximum. So by choosing epsilon arbitrarily small, we get an interval whose length is (arbitrarily close to) 1.0.
4)

 `3` `{1,4.3,7.2,95.4,534.0}` `{72, 83, 19, 25.3, 624.0} `
`Returns: 1.4500000000000002`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=3565

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=6554&pm=3565

dgoodman

#### Testers:

PabloGilberto , lbackstrom , vorthys