<p>Alice is throwing <code>n</code> darts on a very large wall. You are given an array <code>darts</code> where <code>darts[i] = [x<sub>i</sub>, y<sub>i</sub>]</code> is the position of the <code>i<sup>th</sup></code> dart that Alice threw on the wall.</p>

<p>Bob knows the positions of the <code>n</code> darts on the wall. He wants to place a dartboard of radius <code>r</code> on the wall so that the maximum number of darts that Alice throws lie&nbsp;on the dartboard.</p>

<p>Given the integer <code>r</code>, return <em>the maximum number of darts that can lie on the dartboard</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/04/29/sample_1_1806.png" style="width: 248px; height: 211px;" />
<pre>
<strong>Input:</strong> darts = [[-2,0],[2,0],[0,2],[0,-2]], r = 2
<strong>Output:</strong> 4
<strong>Explanation:</strong> Circle dartboard with center in (0,0) and radius = 2 contain all points.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/04/29/sample_2_1806.png" style="width: 306px; height: 244px;" />
<pre>
<strong>Input:</strong> darts = [[-3,0],[3,0],[2,6],[5,4],[0,9],[7,8]], r = 5
<strong>Output:</strong> 5
<strong>Explanation:</strong> Circle dartboard with center in (0,4) and radius = 5 contain all points except the point (7,8).
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= darts.length &lt;= 100</code></li>
	<li><code>darts[i].length == 2</code></li>
	<li><code>-10<sup>4</sup> &lt;= x<sub>i</sub>, y<sub>i</sub> &lt;= 10<sup>4</sup></code></li>
	<li>All the <code>darts</code>&nbsp;are unique</li>
	<li><code>1 &lt;= r &lt;= 5000</code></li>
</ul>

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));
  }
};
12700