Skip to content

1453. Maximum Number of Darts Inside of a Circular Dartboard 👎

  • Time: $O(n^3)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
struct Point {
  double x;
  double y;
  Point(double x, double y) : x(x), y(y) {}
};

class Solution {
 public:
  int numPoints(vector<vector<int>>& darts, int r) {
    int ans = 1;
    vector<Point> points = convertToPoints(darts);

    for (int i = 0; i < points.size(); ++i)
      for (int j = i + 1; j < points.size(); ++j)
        for (const Point& c : getCircles(points[i], points[j], r)) {
          int count = 0;
          for (const Point& point : points)
            if (dist(c, point) - r <= kErr)
              ++count;
          ans = max(ans, count);
        }

    return ans;
  }

 private:
  static constexpr double kErr = 1e-6;

  vector<Point> convertToPoints(const vector<vector<int>>& darts) {
    vector<Point> points;
    for (const vector<int>& dart : darts)
      points.emplace_back(dart[0], dart[1]);
    return points;
  }

  vector<Point> getCircles(const Point& p, const Point& q, int r) {
    if (dist(p, q) - 2.0 * r > kErr)
      return {};
    const Point m{(p.x + q.x) / 2, (p.y + q.y) / 2};
    const double distCM = sqrt(pow(r, 2) - pow(dist(p, q) / 2, 2));
    const double alpha = atan2(p.y - q.y, q.x - p.x);
    return {Point{m.x - distCM * sin(alpha), m.y - distCM * cos(alpha)},
            Point{m.x + distCM * sin(alpha), m.y + distCM * cos(alpha)}};
  }

  double dist(const Point& p, const Point& q) {
    return sqrt(pow(p.x - q.x, 2) + pow(p.y - q.y, 2));
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Point {
  public double x = 0;
  public double y = 0;
  public Point(double x, double y) {
    this.x = x;
    this.y = y;
  }
}

class Solution {
  public int numPoints(int[][] darts, int r) {
    int ans = 1;
    List<Point> points = convertToPoints(darts);

    for (int i = 0; i < points.size(); ++i)
      for (int j = i + 1; j < points.size(); ++j)
        for (Point c : getCircles(points.get(i), points.get(j), r)) {
          int count = 0;
          for (Point point : points)
            if (dist(c, point) - r <= kErr)
              ++count;
          ans = Math.max(ans, count);
        }

    return ans;
  }

  private static final double kErr = 1e-6;

  private List<Point> convertToPoints(int[][] darts) {
    List<Point> points = new ArrayList<>();
    for (int[] dart : darts)
      points.add(new Point(dart[0], dart[1]));
    return points;
  }

  private Point[] getCircles(Point p, Point q, int r) {
    if (dist(p, q) - 2.0 * r > kErr)
      return new Point[] {};
    Point m = new Point((p.x + q.x) / 2, (p.y + q.y) / 2);
    final double distCM = Math.sqrt(Math.pow(r, 2) - Math.pow(dist(p, q) / 2, 2));
    final double alpha = Math.atan2(p.y - q.y, q.x - p.x);
    return new Point[] {new Point(m.x - distCM * Math.sin(alpha), m.y - distCM * Math.cos(alpha)),
                        new Point(m.x + distCM * Math.sin(alpha), m.y + distCM * Math.cos(alpha))};
  }

  private double dist(Point p, Point q) {
    return Math.sqrt(Math.pow(p.x - q.x, 2) + Math.pow(p.y - q.y, 2));
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Point:
  def __init__(self, x: float, y: float):
    self.x = x
    self.y = y


class Solution:
  def numPoints(self, darts: list[list[int]], r: int) -> int:
    kErr = 1e-6
    ans = 1
    points = [Point(x, y) for x, y in darts]

    def dist(p: Point, q: Point) -> float:
      return ((p.x - q.x)**2 + (p.y - q.y)**2)**0.5

    def getCircles(p: Point, q: Point) -> list[Point]:
      if dist(p, q) - 2.0 * r > kErr:
        return []
      m = Point((p.x + q.x) / 2, (p.y + q.y) / 2)
      distCM = (r**2 - (dist(p, q) / 2)**2)**0.5
      alpha = math.atan2(p.y - q.y, q.x - p.x)
      return [Point(m.x - distCM * math.sin(alpha), m.y - distCM * math.cos(alpha)),
              Point(m.x + distCM * math.sin(alpha), m.y + distCM * math.cos(alpha))]

    for i in range(len(points)):
      for j in range(i + 1, len(points)):
        for c in getCircles(points[i], points[j]):
          count = 0
          for point in points:
            if dist(c, point) - r <= kErr:
              count += 1
          ans = max(ans, count)

    return ans