808. Where to Stand the Mast

A village has n houses; house i stands at (x[i], y[i]) with y[i] >= 1, so no house sits on the road. The road is the whole x axis, and one mast must be planted somewhere on it. A straight cable runs from the mast to each house.

Print the smallest possible total cable length, to exactly 4 digits after the decimal point.

houses (0,5) -> 5.0000 houses (-3,4) (3,4) -> 10.0000 houses (0,1) (10,1) -> 10.1980

The total for a mast at x is

f(x) = sqrt((x - x[0])^2 + y[0]^2) + ... + sqrt((x - x[n-1])^2 + y[n-1]^2)

## Why the position is not what is asked for, and that is deliberate

Near its minimum f is almost flat, so a position that is wrong by 10^-4 changes the total by about 10^-8. Asking for the position would be asking for a number the arithmetic cannot pin down; asking for the total is a question a double answers precisely. Recognising which of two quantities is the well-conditioned one is the skill on offer here.

## Why binary search applies to a function with no threshold in it

There is no predicate in the statement at all. Make one out of the slope.

f is a sum of functions each of which is convex in x, so f is convex, so its derivative

g(x) = (x - x[0]) / sqrt((x - x[0])^2 + y[0]^2) + ... + (x - x[n-1]) / sqrt((x - x[n-1])^2 + y[n-1]^2)

is non-decreasing. Every term is (x - x[i]) divided by something strictly positive, since y[i] >= 1 keeps the square root away from zero, and each term rises with x. So g is the monotone function this topic needs, and the minimum of f sits where g crosses zero.

The predicate is g(x) < 0, meaning "still going downhill, move right". It is true on an initial stretch and false after it.

## The bounds

lo = min(x[i]), hi = max(x[i]).

Below the leftmost house every term of g is negative, so f is still falling and the minimum cannot be there. Above the rightmost house every term is positive. The crossing is therefore inside the range spanned by the houses, and with one house it is at that house.

## Why not a ternary search on f itself

Ternary search also works on a convex function, and it is the usual answer. It keeps two thirds of the interval per round instead of one half, so it needs about 1.7 times as many evaluations for the same precision, and each round evaluates f twice rather than g once. Searching the derivative is the cheaper route whenever the derivative is available in closed form, which for this shape it is.

## The boundary that breaks a careless implementation

n = 1. The interval collapses to a single point, the loop runs a hundred times on an empty range, and the answer is simply y[0]. Nothing special is needed, which is worth checking rather than assuming.

The second is the division. If a house were allowed on the road, y[i] = 0, then at x = x[i] the term is 0 / 0. The constraint y[i] >= 1 is what keeps the derivative defined everywhere, and it is why the statement says it.

## Related problems

Problem 802 also searches a monotone real function for a crossing, but there the function is given directly rather than being the slope of the one you care about.

## Cost

Time O(100 * n). Space O(n).

Constraints - `1 ≤ n ≤ 1000` - `-1000 ≤ x[i] ≤ 1000` - `1 ≤ y[i] ≤ 1000` - every answer is at least `10^-6` away from a halfway rounding point at 4 digits