Maximum number of darts inside of a circular dartboard

Array Math Geometry

40.4% acceptance

Feb 25, 2026

159

277

You are given an array darts of size n and an integer r where darts[i] = [xi, yi] are coordinates of a dart. Return the maximum number of darts that can lie on the dartboard if the dartboard is a circle with radius r.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn num_points(darts: Vec<Vec<i32>>, r: i32) -> i32 {
    let n = darts.len();
    if n == 1 { return 1; }
    let r = r as f64;
    let pts: Vec<(f64, f64)> = darts.iter().map(|d| (d[0] as f64, d[1] as f64)).collect();

    let count_in_circle = |cx: f64, cy: f64| -> i32 {
      pts.iter().filter(|&&(x, y)| {
        let dx = x - cx;
        let dy = y - cy;
        dx * dx + dy * dy <= r * r + 1e-6
      }).count() as i32
    };

    let mut ans = 1;
    for i in 0..n {
      for j in (i + 1)..n {
        let (ax, ay) = pts[i];
        let (bx, by) = pts[j];
        let dx = bx - ax;
        let dy = by - ay;
        let d = (dx * dx + dy * dy).sqrt();
        if d > 2.0 * r { continue; }
        let mx = (ax + bx) / 2.0;
        let my = (ay + by) / 2.0;
        let h = (r * r - (d / 2.0) * (d / 2.0)).sqrt();
        let px = -dy / d * h;
        let py = dx / d * h;
        ans = ans.max(count_in_circle(mx + px, my + py));
        ans = ans.max(count_in_circle(mx - px, my - py));
      }
    }
    ans
  }
}