円がかかわる交差判定・交点

//@require intersection.cc
std::vector<P> crosspointCL(const C &c, const L &l) {
    std::vector<P> res;
    ld d = distanceLP(l, c.p);      // 中心と直線の距離
    if (std::abs(d - c.r) < eps) {  // 触れている
        res.push_back(projection(l, c.p));
        return res;
    }
    if (d > c.r) return res;  // 離れている
    P h = projection(l, c.p);
    P u = std::sqrt(c.r * c.r - d * d) * (l[1] - l[0]) / std::abs(l[1] - l[0]);
    res.push_back(h + u);
    res.push_back(h - u);
    return res;
}

int intersectCC(const C &c1, const C &c2) {
    ld d = std::abs(c1.p - c2.p), r1 = c1.r, r2 = c2.r;
    if (r1 + r2 < d) return 0;                   // 離れている
    if (std::abs(r1 + r2 - d) < eps) return -2;  // 外接
    if (std::abs(d + r1 - r2) < eps) return +1;  // c1 が c2 の中で内接
    if (std::abs(d + r2 - r1) < eps) return -1;  // c2 が c1 の中で内接
    if (d + r1 < r2) return +3;                  // c1 が c2 の中
    if (d + r2 < r1) return -3;                  // c2 が c1 の中
    return 2;                                    // 2つの交点を持つ
}

std::vector<P> crosspointCC(const C &c1, const C &c2) {
    std::vector<P> res;
    ld r1 = c1.r, r2 = c2.r, d = std::abs(c1.p - c2.p);
    if (std::abs(c1.p - c2.p) < 0) return res;  // 中心が同じ
    int i = intersectCC(c1, c2);
    if (i == +1 || i == -1) {  // 内接
        if (r2 < r1)
            res.push_back(c1.p + r1 / d * (c2.p - c1.p));
        else
            res.push_back(c2.p + r2 / d * (c1.p - c2.p));
        return res;
    }
    if (i == -2) {  // 外接
        res.push_back((c1.p * c1.r + c2.p * c2.r) / (c1.r + c2.r));
        return res;
    }
    if (i == 0 || i == +3 || i == -3) {  // 共通部分なし || 内部
        return res;
    }
    // 2つの交点を持つ
    P p = c1.p - c2.p;
    ld A = -2. * p.real(), B = 2 * p.imag();
    ld C = norm(c1.p) - norm(c2.p) - r1 * r1 + r2 * r2;
    return crosspointCL(c1, L(A, B, C));  // Ax + By + C = 0
}