<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:
    double dist(vector<int> &p1, vector<int> &p2) {
        return sqrt((double)((p1[0]-p2[0])*(p1[0]-p2[0]) + (p1[1]-p2[1])*(p1[1]-p2[1])));
    }
    double dist(vector<double> &p1, vector<int> &p2) {
        return sqrt((double)((p1[0]-p2[0])*(p1[0]-p2[0]) + (p1[1]-p2[1])*(p1[1]-p2[1])));
    }

    pair<vector<double>, vector<double>> getCenter(vector<int> & a, vector<int> &b, int r) {
		vector<double> midP(2);
		pair<vector<double>, vector<double>> res = {{0,0},{0,0}};
		midP[0] = (double)(a[0] + b[0]) / 2.0;
        midP[1] = (double)(a[1] + b[1]) / 2.0;
		double theta = atan2(a[1] - b[1], b[0] - a[0]);
		double tmp = dist(a, b) / 2;
		double d = sqrt(r * r - tmp*tmp);
		res.first[0] = midP[0] - d*sin(theta);
		res.first[1] = midP[1] - d*cos(theta);
		res.second[0] = midP[0] + d*sin(theta);
		res.second[1] = midP[1] + d*cos(theta);
		return res;
	}

    int numPoints(vector<vector<int>>& pts, int r) {
        int sz = pts.size(), res = 1;
        const double tolr = 1e-6, PI = 3.141592654;
        if(sz < 1) return 0;
        for (int i = 0; i < sz; i++) {
            for (int j = i+1; j < sz; j++) {
                double d = dist(pts[i], pts[j]), d2 = d/2, b, m1, m2, theta, bx, by; 
                if (d > 2*r + tolr)
                    continue;
                
                vector<double> C1, C2, midP, C1cpy, C2cpy;
                midP = {(pts[i][0]+pts[j][0])/2.0, (pts[i][1]+pts[j][1])/2.0 };
                b = sqrt(r*r-d2*d2);
                theta = atan2(pts[i][1]-pts[j][1], pts[j][0]-pts[i][0]); 
                bx = b*sin(theta);   //bx / b = sin(th)
                by = b*cos(theta);
                C1cpy = C1 = {midP[0] + bx, midP[1] + by};
                C2cpy = C2 = {midP[0] - bx, midP[1] - by};
                
                //pair<vector<double>, vector<double>> centers;
                //centers = getCenter(pts[i], pts[j], r);
                //C1 = centers.first; C2 = centers.second;
                int cnt = 2;
                for(int k = 0; k < sz; k++) {
                    if (k == i || k == j) continue;
                    double dd = dist(C1, pts[k]);
                    if (dd <= r+tolr) cnt++;
                }
                res = max(res, cnt);
                cnt = 2;
                for(int k = 0; k < sz; k++) {
                    if (k == i || k == j) continue;
                    double dd = dist(C2, pts[k]);
                    if (dd <= r+tolr) cnt++;
                }
                res = max(res, cnt);                                
            }
        }
        return res;
    }
};
15800