<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>

class Solution {
public:
  vector<pair<double, double>> findCenters(int i, int j, vector<vector<int>>& darts, int r) {
    double x1 = darts[i][0], y1 = darts[i][1], x2 = darts[j][0], y2 = darts[j][1];

    int dx = darts[i][0] - darts[j][0];
    int dy = darts[i][1] - darts[j][1];
    int d2 = dx * dx + dy * dy;
    if (4 * r * r < d2) return {};
    if (4 * r * r == d2) {
      return {{(x1 + x2) / 2.0, (y1 + y2) / 2.0}};
    }

    double h = sqrt(r * r - d2 / 4.0);
    double d = sqrt(d2);
    double cx1 = (x1 + x2) / 2.0 - h * (y2 - y1) / d;
    double cy1 = (y1 + y2) / 2.0 + h * (x2 - x1) / d;
    double cx2 = (x1 + x2) / 2.0 + h * (y2 - y1) / d;
    double cy2 = (y1 + y2) / 2.0 - h * (x2 - x1) / d;

    return {{cx1, cy1}, {cx2, cy2}};
  }

  int countPoints(double& x, double& y, vector<vector<int>>& darts, int r) {
    double rr = r * r;
    int cnt = 0;
    for (auto& p : darts) {
      double dx = x - p[0];
      double dy = y - p[1];
      double d = dx * dx + dy * dy;
      if (d <= rr) {
        cnt++;
      }
    }
    return cnt;
  }

  int numPoints(vector<vector<int>>& darts, int r) {
    int n = darts.size();
    int best = 1;

    for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
        auto centers = findCenters(i, j, darts, r);
        for (auto& [x, y] : centers) {
          best = max(best, countPoints(x, y, darts, r));
        }
      }
    }      

    return best;
  }
};

12200