Erect the fence

Array Math Geometry

52.7% acceptance

Jan 13, 2026

1542

649

You are given an array trees where trees[i] = [xi, yi] represents the location of a tree in the garden. Fence the entire garden using the minimum length of rope, as it is expensive. The garden is well-fenced only if all the trees are enclosed. Return the coordinates of trees that are exactly located on the fence perimeter. You may return the answer in any order.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn outer_trees(trees: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    let mut pts = trees;
    pts.sort_unstable_by(|a, b| a[0].cmp(&b[0]).then(a[1].cmp(&b[1])));
    let n = pts.len();
    if n <= 1 { return pts; }
    fn cross(o: &[i32], a: &[i32], b: &[i32]) -> i64 {
      (a[0]-o[0]) as i64 * (b[1]-o[1]) as i64 - (a[1]-o[1]) as i64 * (b[0]-o[0]) as i64
    }
    let mut hull: Vec<Vec<i32>> = Vec::new();
    for p in &pts {
      while hull.len() >= 2 && cross(&hull[hull.len()-2], &hull[hull.len()-1], p) < 0 {
        hull.pop();
      }
      hull.push(p.clone());
    }
    let lower_len = hull.len();
    for p in pts.iter().rev() {
      while hull.len() > lower_len && cross(&hull[hull.len()-2], &hull[hull.len()-1], p) < 0 {
        hull.pop();
      }
      hull.push(p.clone());
    }
    hull.pop();
    hull.sort_unstable();
    hull.dedup();
    hull
  }
}