<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:
    const double total=1e-6;
    double R;
    struct point{
        double x,y;
    };
    vector<point>points;
    double dist(const point&a,const point&b){
        return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
    }
    pair<point,point> getCenter(const point&a,const point&b){
        point mid;
        pair<point,point>res;
        mid.x=(a.x+b.x)/2,mid.y=(a.y+b.y)/2;
        double theta=atan2(a.y-b.y,b.x-a.x);
        double temp=dist(a,b)/2.0;
        double d=sqrt(R*R-temp*temp);
        res.first.x=mid.x-d*sin(theta);
        res.first.y=mid.y-d*cos(theta);
        res.second.x=mid.x+d*sin(theta);
        res.second.y=mid.y+d*cos(theta);
        return res;
    }
    int numPoints(vector<vector<int>>& darts, int r) {
        int n=darts.size();
        R=double(r);
        points.resize(n);
        for(int i=0;i<n;i++){
            points[i].x=darts[i][0];
            points[i].y=darts[i][1];
        }
        int ans=1;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(i==j||dist(points[i],points[j])-2*R>total)continue;
                int cnt=0;
                auto p=getCenter(points[i],points[j]);
                for(int k=0;k<n;k++){
                    if(dist(points[k],p.second)-R<=total)++cnt;
                }
                ans=max(ans,cnt);
            }
        }
        return ans;
    }
};
10400