Erect the fence ii

Array Math Geometry

51.6% acceptance

Mar 31, 2026

You are given a 2D integer array trees where trees[i] = [xi, yi] represents the location of the ith tree in the garden. You are asked to fence the entire garden using the minimum length of rope possible. The garden is well-fenced only if all the trees are enclosed and the rope used forms a perfect circle. A tree is considered enclosed if it is inside or on the border of the circle. More formally, you must form a circle using the rope with a center (x, y) and radius r where all trees lie inside or on the circle and r is minimum. Return the center and radius of the circle as a length 3 array [x, y, r]. Answers within 10-5 of the actual answer will be accepted.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn outer_trees(trees: Vec<Vec<i32>>) -> Vec<f64> {
    let pts: Vec<(f64, f64)> = trees.iter().map(|t| (t[0] as f64, t[1] as f64)).collect();
    let (cx, cy, r) = min_enclosing_circle(&pts);
    vec![cx, cy, r]
  }
}

fn min_enclosing_circle(pts: &[(f64, f64)]) -> (f64, f64, f64) {
  if pts.is_empty() {
    return (0.0, 0.0, 0.0);
  }
  let mut ps: Vec<(f64, f64)> = pts.to_vec();
  // Shuffle for expected O(n)
  use std::collections::hash_map::DefaultHasher;
  use std::hash::{Hash, Hasher};
  let mut seed = ps.len() as u64;
  for i in (1..ps.len()).rev() {
    seed ^= seed << 13;
    seed ^= seed >> 7;
    seed ^= seed << 17;
    let j = (seed as usize) % (i + 1);
    ps.swap(i, j);
  }

  let mut cx = ps[0].0;
  let mut cy = ps[0].1;
  let mut r = 0.0;

  for i in 1..ps.len() {
    if dist(cx, cy, ps[i].0, ps[i].1) > r + 1e-7 {
      cx = ps[i].0;
      cy = ps[i].1;
      r = 0.0;
      for j in 0..i {
        if dist(cx, cy, ps[j].0, ps[j].1) > r + 1e-7 {
          cx = (ps[i].0 + ps[j].0) / 2.0;
          cy = (ps[i].1 + ps[j].1) / 2.0;
          r = dist(cx, cy, ps[i].0, ps[i].1);
          for k in 0..j {
            if dist(cx, cy, ps[k].0, ps[k].1) > r + 1e-7 {
              let (x, y, rr) = circumcircle(ps[i], ps[j], ps[k]);
              cx = x;
              cy = y;
              r = rr;
            }
          }
        }
      }
    }
  }
  (cx, cy, r)
}

fn dist(x1: f64, y1: f64, x2: f64, y2: f64) -> f64 {
  ((x1 - x2).powi(2) + (y1 - y2).powi(2)).sqrt()
}

fn circumcircle(a: (f64, f64), b: (f64, f64), c: (f64, f64)) -> (f64, f64, f64) {
  let ax = a.0; let ay = a.1;
  let bx = b.0; let by = b.1;
  let cxx = c.0; let cyy = c.1;
  let d = 2.0 * (ax * (by - cyy) + bx * (cyy - ay) + cxx * (ay - by));
  if d.abs() < 1e-10 {
    // Collinear: return circle through the two farthest points
    let d1 = dist(ax, ay, bx, by);
    let d2 = dist(bx, by, cxx, cyy);
    let d3 = dist(ax, ay, cxx, cyy);
    if d1 >= d2 && d1 >= d3 {
      return ((ax + bx) / 2.0, (ay + by) / 2.0, d1 / 2.0);
    } else if d2 >= d3 {
      return ((bx + cxx) / 2.0, (by + cyy) / 2.0, d2 / 2.0);
    } else {
      return ((ax + cxx) / 2.0, (ay + cyy) / 2.0, d3 / 2.0);
    }
  }
  let ux = ((ax * ax + ay * ay) * (by - cyy) + (bx * bx + by * by) * (cyy - ay) + (cxx * cxx + cyy * cyy) * (ay - by)) / d;
  let uy = ((ax * ax + ay * ay) * (cxx - bx) + (bx * bx + by * by) * (ax - cxx) + (cxx * cxx + cyy * cyy) * (bx - ax)) / d;
  let r = dist(ux, uy, ax, ay);
  (ux, uy, r)
}