<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 {
private:
	static inline double Sqr(double val) {
		return val * val;
	}

	static inline double Sqr_Distance(double x1, double y1, double x2, double y2) {
		return Sqr(x2 - x1) + Sqr(y2 - y1);
	}
public:
	int numPoints(vector<vector<int>>& darts, int r) {
		double Sqr_R = Sqr(r);

		size_t max = 1;
		for (size_t i = 0; i != darts.size(); ++i) {
			auto& i_pos = darts[i];
			double x0 = i_pos[0];
			double y0 = i_pos[1];
			for (size_t j = i + 1; j != darts.size(); ++j) {
				auto& j_pos = darts[j];
				double x = j_pos[0];
				double y = j_pos[1];
				auto sqr_dist = Sqr_Distance(x0, y0, x, y);
				if (sqr_dist > Sqr_R * 4) continue;

				auto dx = x - x0;
				auto dy = y - y0;
				auto dist = sqrt(sqr_dist);
				auto h = sqrt(Sqr_R - Sqr(dist / 2));
				auto hdx_d = h * dx / dist;
				auto hdy_d = h * dy / dist;

				auto xC1 = x0 + dx / 2 + hdy_d;
				auto xC2 = x0 + dx / 2 - hdy_d;
				auto yC1 = y0 + dy / 2 - hdx_d;
				auto yC2 = y0 + dy / 2 + hdx_d;

				size_t count1 = 0;
				size_t count2 = 0;
				for (auto& pos : darts) {
					x = pos[0];
					y = pos[1];
					#define EPS 1e-6
					if ((Sqr_Distance(xC1, yC1, x, y) - EPS) < Sqr_R) ++count1;
					if ((Sqr_Distance(xC2, yC2, x, y) - EPS) < Sqr_R) ++count2;
				}
				if (count1 > max) max = count1;
				if (count2 > max) max = count2;
			}
		}
		return max;
	}
};
9900