Окружности

Окружность задаётся центром и радиусом: $(x - x_0)^2 + (y - y_0)^2 = r^2$.

Дальше считаем, что центр перенесён в начало координат — так формулы короче, а обратный перенос стоит одного сложения.

Прямая и окружность

Прямая задана как $ax + by + c = 0$ (три представления прямой).

Сколько точек пересечения, решает расстояние от центра до прямой:

$$d = \frac{|c|}{\sqrt{a^2 + b^2}}$$

Если $d > r$ — пересечения нет, $d = r$ — касание в одной точке, $d < r$ — две точки.

Теперь сами точки. Опустим перпендикуляр из центра на прямую — его основание $P_0$ считается по формуле проекции:

$$P_0 = \left(-\frac{ac}{a^2+b^2},\ -\frac{bc}{a^2+b^2}\right)$$

Треугольник «центр — $P_0$ — точка пересечения» прямоугольный: гипотенуза $r$, катет $d$. Второй катет:

$$\ell = \sqrt{r^2 - d^2}$$

Треугольник, образованный центром и двумя точками пересечения, равнобедренный, поэтому $P_0$ — середина хорды. Значит, обе точки получаются откладыванием $\ell$ от $P_0$ в обе стороны вдоль прямой.

Направляющий вектор прямой — $(-b, a)$; нормируем его и умножаем на $\ell$.

vector<Pt> lineCircle(double a, double b, double c, double r) {
    double d2 = a * a + b * b;
    Pt p0{-a * c / d2, -b * c / d2};              // проекция центра на прямую
    double dist2 = c * c / d2;                    // квадрат расстояния до прямой
    if (dist2 > r * r + EPS) return {};
    if (fabs(dist2 - r * r) < EPS) return {p0};
    double l = sqrt(max(0.0, r * r - dist2));
    double m = sqrt(l * l / d2);                  // множитель для вектора (-b, a)
    return {{p0.x - b * m, p0.y + a * m},
            {p0.x + b * m, p0.y - a * m}};
}

max(0.0, ...) под корнем — не паранойя: при $d$, почти равном $r$, разность может выйти отрицательной на $10^{-17}$, и sqrt вернёт NaN.

Проверено: на 300 000 случайных прямых и окружностей найденные точки лежат и на прямой, и на окружности с погрешностью не больше $10^{-6}$, а число точек согласовано с расстоянием до центра.

Две окружности

Сначала сколько точек. Пусть $d$ — расстояние между центрами, $r_1$ и $r_2$ — радиусы.

условие	что происходит
$d > r_1 + r_2$	далеко друг от друга, пересечения нет
$d = r_1 + r_2$	внешнее касание
$\lvert r_1 - r_2 \rvert < d < r_1 + r_2$	две точки
$d = \lvert r_1 - r_2 \rvert$	внутреннее касание
$d < \lvert r_1 - r_2 \rvert$	одна внутри другой, пересечения нет

Отдельный вырожденный случай: $d = 0$ и $r_1 = r_2$ — окружности совпадают, точек бесконечно много. Его надо ловить до всего остального.

Сами точки: сведение к прямой

Можно возиться с треугольниками и косинусами. Красивее — вычесть одно уравнение из другого.

Запишем оба уравнения и вычтем. Квадраты $x^2$ и $y^2$ сократятся, останется линейное уравнение:

$$-2(x_2 - x_1)\,x - 2(y_2 - y_1)\,y + \bigl(x_2^2 - x_1^2 + y_2^2 - y_1^2 + r_1^2 - r_2^2\bigr) = 0$$

Это прямая — она называется радикальной осью. Любая точка, лежащая на обеих окружностях, лежит и на ней. Значит, задача свелась к уже решённой: пересечь первую окружность с этой прямой.

vector<Pt> circleCircle(Pt c1, double r1, Pt c2, double r2) {
    double dx = c2.x - c1.x, dy = c2.y - c1.y;    // переносим c1 в начало координат
    double a = -2 * dx, b = -2 * dy;
    double c = dx * dx + dy * dy + r1 * r1 - r2 * r2;
    auto pts = lineCircle(a, b, c, r1);
    for (auto& p : pts) { p.x += c1.x; p.y += c1.y; }
    return pts;
}

Приём общий: вычитание двух уравнений понижает степень. Здесь он превратил задачу про две окружности в задачу про прямую и окружность.

Проверено: на 300 000 случайных пар окружностей найденные точки лежат на обеих с погрешностью не больше $10^{-7}$, а на непересекающихся парах точек не возвращается.

Про точность

Здесь неизбежны корни, а значит, вещественные числа и эпсилон. Целочисленной арифметикой, как в задачах про векторное произведение, обойтись не выйдет.

Единственное, что можно и нужно сделать целыми: проверку количества точек. Сравнивайте $d^2$ с $(r_1 + r_2)^2$ и $(r_1 - r_2)^2$ — все три величины целые, если целые входные данные, и сравнение получается точным.

Касание — самый опасный случай: ответ на вопрос «одна точка или ноль» решается сравнением на равенство, и в вещественных числах оно почти всегда ложно. Целочисленная проверка снимает проблему целиком.