# 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>& darts, int r) { int ans = 1; vector 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 convertToPoints(const vector>& darts) { vector points; for (const vector& dart : darts) points.emplace_back(dart[0], dart[1]); return points; } vector 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 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 convertToPoints(int[][] darts) { List 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