<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:
    bool getP(double &dx0, double &dy0, double &dx1, double &dy1, double x1, double y1, double x2, double y2, double r)
    {
        double L = (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2);
        if (L > 4 * r * r) return false;
        if (x1 == x2)
        {
            double A = 1.0;
            double B = -2 * x1;
            double cy = (y1+y2)/2;
            double C = x1*x1 + (cy-y1)*(cy-y1)-r*r;
            double delta = sqrt(B*B-4*A*C);
            dx0 = (-B + delta) / (2*A);
            dy0 = cy;
            dx1 = (-B - delta) / (2*A);
            dy1 = cy;
        }
        else
        {
            double c1 = (x2*x2 - x1*x1 + y2*y2 - y1*y1) / (2*(x2-x1));
            double c2 = (y2-y1) / (x2-x1);
            double A = (c2*c2 + 1);
            double B = (2 * x1*c2 - 2*c1*c2 - 2*y1);
            double C = x1*x1 - 2 * x1*c1 + c1*c1 + y1*y1 - r*r;
            double delta = sqrt(B*B-4*A*C);
            dy0 = (-B + delta) / (2*A);
            dx0 = c1 - c2 * dy0;
            dy1 = (-B - delta) / (2*A);
            dx1 = c1 - c2 * dy1;
        }
        return true;
    }
    bool inside(double x, double y, double cx, double cy, double r)
    {
        if ((x - cx) * (x - cx) + (y - cy) * (y - cy) <= r * r + 1e-7) return true;
        return false;
    }
    int numPoints(vector<vector<int>>& darts, int r) {
        int n = darts.size();
        int res = 1;
        for (int i = 0; i < n; i ++)
            for (int j = i+1; j < n; j ++)
            {
                double x0, y0, x1, y1;
                bool has = getP(x0, y0, x1, y1, darts[i][0], darts[i][1], darts[j][0], darts[j][1], r);
                if (has)
                {
                    int num0 = 0;
                    int num1 = 0;
                    for (int k = 0; k < n; k ++)
                    {
                        if (inside(darts[k][0], darts[k][1], x0, y0, r)) num0 ++;
                        if (inside(darts[k][0], darts[k][1], x1, y1, r)) num1 ++;
                    }
                    //printf("%d %d (%lf %lf) %d (%lf %lf) %d\n", i, j , x0, y0, num0, x1, y1, num1);
                    res = max(res, max(num0, num1));
                }
            }
        return res;
    }
};
10100