Проверка пересечения треугольника с окружностью

[escanor]

На плоскости заданы множество точек и окружность радиусом R с центром в начале координат. Построить множество всех треугольников с вершинами в заданных точках, имеющих непустое пересечение с окружностью.

#include <iostream>
#include <cstdlib>
#include <clocale>
#include <ctime>
#include <cmath>
#include <string>
#include <vector>
using namespace std;
struct pnt
{
    int x, y;
    int in;
};

int main()
{
    srand(time(0));
    vector<pnt> p;
    unsigned int n;
    double r;
    cout << "Points count: ";
    cin >> n;
    cout << "Radius: ";
    cin >> r;

    for (unsigned int i = 0; i < n; ++i)
    {
        pnt t;
        t.x = rand() % 30 - 10;
        t.y = rand() % 30 - 10;
        t.in = t.x * t.x + t.y * t.y < r* r;
        p.push_back(t);
        cout << "(" << t.x << ", " << t.y << ")\n";
    }
    cout << "Triangles:\n";
    for (unsigned int i = 0; i < n; ++i)
    {
        pnt a = p[i];
        for (unsigned int j = i + 1; j < n; ++j)
        {
            pnt b = p[j];
            for (unsigned int k = j + 1; k < n; ++k)
            {
                pnt c = p[k];
                int in = a.in + b.in + c.in;
                if (in == 1 || in == 2)
                {
                    cout << "[(" << a.x << "," << a.y
                        << ")(" << b.x << "," << b.y
                        << ")(" << c.x << "," << c.y << ")]\n";
                }
            }
        }
    }
    system("pause");
    return 0;
}

в данной программе не проверяется одно из условий а именно : когда вершины треугольника лежат вне окружности а пересечение по ребру присутствует
вообщем знает ли кто-нибудь формулу для проверки этого условия я уже долгое время не могу придумать чего-то нормального , прошу помощи!

[macomics]

ra = a.x*a.x + a.y*a.y;
rb = b.x*b.x + b.y*b.y;
rc = c.x*c.x + c.y*c.y;
if ((ra <= r*r) && (rb <= r*r) && (rc <= r*r)) треугольник внутри окружности
else if ((ra > r*r) && (rb > r*r) && (rc > r*r)) треугольник вне окружности
else треугольник пересекает окружность

abs тут не нужен. Работаем с квадратами.
Для проверки пересечения стороны с окружностью надо найти корни системы

x*x+y*y=r*r
k1*x+b1=y
k1*a.x+b1=a.y
k1*b.x+b1=b.y

Для стороны AB

x*x+y*y=r*r
k2*x+b2=y
k2*b.x+b2=b.y
k2*c.x+b2=c.y

Для стороны BС

x*x+y*y=r*r
k3*x+b3=y
k3*a.x+b3=a.y
k3*c.x+b3=c.y

Для стороны AС

[ViktorR]

Возможно подойдёт и такой алгоритм:
1. Для выбранной точки А вне окружности находите точки окружности, через которые пройдут касательные из заданной точки (в нашем случае т.А).
Пусть это будут т.Б. или т.С.
Посмотрите, например тут https://math.stackexchange.com/quest...es-through-a-g
2. Двигаясь по точкам, которые вне окружности, например, по часовой стрелке, можно "распознать" следующую точку как точку, которая находится слева или справа от вектора АБ. Для этого можно использовать векторное умножение, посмотрите например тут: https://habr.com/ru/post/144921/

Очевидно, что точки справа (при обходе по часовой стрелке) могут быть вершинами треугольника, сторона которого пересекает окружность. Если векторное умножение даст ноль, то сторона треугольника касается окружности.