Геометрия, Программирование. Помогите мыслёй.

С использованием ООП:

1. Реализовать структуру данных, которая создаёт объект Точки на плоскости заданный парой декартовых координат.

2. Реализовать структуру данных, которая создаёт объект Окружности по Точке на плоскости заданным парой декартовых координат и её радиусу. Реализовать в нём метод площади Окружности.

3. Реализовать структуру данных, которая создаёт объект Треугольника по трём Точкам на плоскости заданных парами декартовых координат.
3.1. Реализовать конструкторы без параметров (инициализация нулями) и с параметрами, который принимает на вход три Точки и выполняет проверку на существование, если проверка не пройдена, точки инициализировать нулями.
3.2. Реализовать в нём методы:
- проверки треугольника на существование;
- расчёта площади треугольника по трём сторонам;
- расчёта полупериметра треугольника;
- включения заданной окружности в площадь ограниченную данным Треугольником;
- вывод данных о треугольнике на экран консоли.
3.3. Реализовать оператор сравнения «меньше» для возможности стандартной сортировки объектов. В качестве параметров сравнения брать площадь треугольников.

4. Создать на базе std::set множество Точек на плоскости и заполнить его имеющимися данными.

5. Создать на базе std::set множество всех возможных Треугольников. Три цикла вам в помощь, перед включением треугольника в множество выполнять проверку на то, что его площадь больше либо равна произведению его полупериметра на радиус Окружности.

6. Выполняя итерации по множеству Треугольников проверять выполнение заданного условия, вызывая для каждого Треугольника метод вхождения окружности в его площадь. Первое же совпадение – есть результат вашего задания.

1. Выбрасываем все точки, лежащие внутри круга.
2. Из оставшихся точек формируем все возможные пары.
3. Выбрасываем пары точек, для которых расстояние от прямой, образованной этими точками, до центра окружности меньше R: https://ru.wikipedia.org/wiki/Расстояние_от_точки_до_прямой_на_плоскости#Прямая_задана_двумя_точками
4. Из оставшихся пар формируем треугольники: три пары должны содержать суммарно три разные точки - получаем тройки вершин анализируемых треугольников.
5. Выбрасываем все треугольники, для которых центр окружности лежит вне этих треугольников: http://cyber-code.ru/tochka_v_treugolnike/
6. Получили искомый список треугольников.
7. Ищем треугольник минимальной площади.

Во-первых, исключить все точки, которые попадают в и на границу окружности.
Во-вторых, создать список из пар точек таких, что не пересекают окружность (ну и расстояние между ними можно сразу посчитать и запомнить).
Далее перебрать все пары отрезков:
1) если у них одна точка общая
2) если две оставшиеся точки образуют отрезок, который имеется в списке отрезков

1. Простой критерий через двухмерное векторное произведение - "точка лежит слева от ребра" - сложность - два умножения и одно сложение.

2. Если точка внутри треугольника, то он лежит слева от всех его ребер, если обходить их по часовой стрелке.

3. Отобранные точки проверяются на расстояние до ребер (два умножения и одно сложение - квадрат расстояния, корень извлекать не нужно. )

4. Треугольник покрывает круг если расстояние от центра до каждого ребра больше радиуса.

Все

Какие ограничения на n, координаты и на время выполнения?

Решения в других ответах имеют временную сложность (если я их правильно понял, конечно) не лучше O(n^3). С таким же успехом можно просто перебрать все тройки точек, отсеять невалидные и найти минимум без всяких промежуточных шагов. Но я предполагаю, что n здесь порядка тысячи или больше, иначе было бы слишком просто. Тогда придётся придумывать что-то неприятное за O(n^2), O(n^2logn) и т. д.