LC 1453. Maximum Number of Darts Inside of a Circular Dartboard
Given 2 points and 1 radius, there will be 2 or 1 or 0 circles where the 2 points are at the boundary. When dist(p0, p1)>2r, there will be 0 circles.
The difficulty is how to get the center of the circle in clean C++ codes. A good class we could use is std::complex<T>. Each point is a vector in the 2d grid.
// d = |p0_p1|
// h = sqrt(r^2 - d^2/4)
// p3_ = (p1_ + p0) / 2.0
// p3_c = p0_p1 * (0, j) * h/d
// c = p3_ + p3_c
using P = complex<double>;
P get_center0(P const &p0, P const &p1, int r) {
auto d = abs(p0 - p1);
auto p3 = (p1 + p0) / 2.0;
auto c = p3 + (p0 - p1) * P(0, 1) * sqrt(r * r - d * d / 4) / d;
return c;
}Some techniques we will use.
// equal is meaningless in double, we use "< epsilon" instead of "<="
dist(p3, c) < r + EPS
// there will be two centers: p3_c = p0_p1 * (0, -j) * h/d
// but it will be covered when we enumerate (j, i)