Best position for a service centre

Array Math Geometry Randomized

35.1% acceptance

Feb 25, 2026

246

274

A delivery company wants to build a new service center in a new city. The company knows the positions of all the customers in this city on a 2D-Map and wants to build the new center in a position such that the sum of the euclidean distances to all customers is minimum. Given an array positions where positions[i] = [xi, yi] is the position of the ith customer on the map, return the minimum sum of the euclidean distances to all customers. In other words, you need to choose the position of the service center [xcentre, ycentre] such that the following formula is minimized: Answers within 10-5 of the actual value will be accepted.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn get_min_dist_sum(positions: Vec<Vec<i32>>) -> f64 {
    let n = positions.len() as f64;
    // Start at centroid
    let mut cx = positions.iter().map(|p| p[0] as f64).sum::<f64>() / n;
    let mut cy = positions.iter().map(|p| p[1] as f64).sum::<f64>() / n;

    let dist_sum = |x: f64, y: f64| -> f64 {
      positions.iter()
        .map(|p| ((p[0] as f64 - x).powi(2) + (p[1] as f64 - y).powi(2)).sqrt())
        .sum()
    };

    let mut step = 1.0f64;
    while step > 1e-7 {
      let mut improved = false;
      for &(dx, dy) in &[(step, 0.0), (-step, 0.0), (0.0, step), (0.0, -step)] {
        if dist_sum(cx + dx, cy + dy) < dist_sum(cx, cy) - 1e-8 {
          cx += dx;
          cy += dy;
          improved = true;
          break;
        }
      }
      if !improved {
        step /= 2.0;
      }
    }
    dist_sum(cx, cy)
  }
}