340. Optimum Location of a Point to Minimize Total Distance

A line is given by the equation a*x + b*y + c = 0 (with a and b not both zero), and n points are given. Find a point P on the line that minimizes the sum of Euclidean distances from P to all n given points, and print that minimum possible total distance rounded to exactly 4 decimal places.

Input: The first line contains three integers a, b, c defining the line a*x + b*y + c = 0. The second line contains an integer n. The next n lines each contain two integers, a point's x and y coordinates. Output: Print a single floating-point number, rounded to exactly 4 decimal places - the minimum total distance from a point on the line to all given points.

1 <= n <= 1000, -1000 <= a, b, c, point coordinates <= 1000, a and b not both 0

The convexity of a SUM of Euclidean-distance functions (each individually convex) is what guarantees a single, well-defined minimum exists - without this convexity guarantee, ternary search would not be a valid technique at all.

Find a point on a given line that minimizes the total distance to a set of given points elsewhere. Brute force: Try a large number of evenly-spaced sample points along the line and pick whichever gives the smallest total distance - this can get a reasonable approximation but never converges to the EXACT minimum precisely enough for a 4-decimal-place answer, unlike a targeted iterative search. Optimised: Since the total-distance function is provably CONVEX (a single smooth valley, no local minima to get stuck in), ternary search - which repeatedly discards a THIRD of the remaining search range based on comparing two interior points - converges exponentially fast toward the true single minimum, reaching high precision in only a few hundred iterations.

The total distance as a function of the line parameter t, f(t), is a sum of convex functions (each Euclidean distance to a fixed point is convex in t) and hence is itself convex, meaning its derivative f'(t) is monotonically non-decreasing. Compute f'(t) analytically as the sum of each point's directional derivative along the line, then binary search for the t where f'(t) crosses from negative to positive, which locates the global minimum without ever having to evaluate f(t) itself at many points. Time: O(n log(1/epsilon)) Space: O(1)

Since f(t) is strictly convex, ternary search can locate its minimum directly by repeatedly comparing f at two probe points within a shrinking interval and discarding the third of the range that cannot contain the minimum, converging geometrically. This avoids computing or trusting a numerically fragile analytical derivative altogether, comparing only function values, which makes it more numerically robust while matching the same asymptotic cost as the derivative-based approach. Time: O(n log(1/epsilon)) Space: O(1)

Parametrize points on the line as P(t) and sample t densely across a large enough range covering all plausible optimal locations (based on the coordinate bounds), computing the total Euclidean distance to all n points at each sample and keeping the minimum found. This is simple to reason about but its accuracy is limited by how fine the sampling step is, and achieving 4-decimal precision this way requires an extremely large number of samples. Time: O(n * (range / step)) Space: O(1)

1. Parametrize every point ON the line by a single variable (like its x-coordinate, using the line's equation to derive the corresponding y). 2. The TOTAL distance from a point on the line to all the given points, as a function of this single parameter, is a SUM of convex (distance) functions - and a sum of convex functions is itself convex, meaning it has exactly one minimum, shaped like a single smooth valley. 3. Use TERNARY search (not binary search) on this parameter: repeatedly narrow the search range by comparing the function's value at two interior points, discarding whichever third of the range can't contain the minimum. 4. Run enough ternary-search iterations (a few hundred) to converge precisely, then round the final minimum total distance to 4 decimal places.

Time: O(n * log(1/epsilon)) - each ternary search iteration costs O(n) to evaluate the total distance to all points, and the number of iterations needed for a desired precision is logarithmic in that precision. Space: O(1) extra space beyond the input points.

Test a vertical line (b = 0, requiring parametrization by y instead of x), n = 1, and n = 1000 for performance and precision of the ternary search.

Be ready to clearly distinguish ternary search (for UNIMODAL/convex continuous functions, narrowing by thirds) from binary search (for discrete monotonic conditions, narrowing by halves) - conflating the two is a common mistake, and recognizing WHEN each applies is the real skill being tested.