Геометрия

Основа

a * b = |a| * |b| * cosA = x1 * x2 + y1 * y2

a ^ b = |a| * |b| * sinA = x1 * y2 - x2 * y1

Пересечение отрезков

Смотрим два знака векторных произведений - должны быть разными

Кроме того, нужно (много ифать) посмотреть, что проекции пересекаются

делать это так:

inter(x1,x2,x3,x4) {

x1 > x2 => swap(x1,x2);

x3 > x4 => swap(x3,x4);

return max(x1,x3) <= min(x2, x4);

}

Уравнение прямой

ax + by + c = 0

построение по двум точкам

a = Ay - By

b = Bx - Ax

c = - aAx - bAy

(a, b) - вектор нормали

(-b, a) - вектор направляющий

пересечение прямых

y = (-A1C2 + A2C1) / (A1B2 - A2B1)

x = (-C1B2 + C2B1) / (A1B2 - A2B1)

проверка на знаменатель - проверка на параллельность

Расстояние от точки до прямой

d(x,y) = abs(ax + by + c) / sqrt(a^2 + b^2)

для вывода берем нормаль, точку, прямую, все аккуратно прибавим

Пересечение прямой и окружности

считаем расстояние от центра до прямой и рассматриваем случаи

1. d > r => точек нет
2. d == r => одна точка касания(идем на r по нормали, но надо проверить, что мы шли не на 180
3. d < r => две точки(встать на прямую как в п.2 и пойти либо влево и вправо на D = sqrt(r * r - d * d)

Пересечение окружностей

1. Совпадение центров (r1 == r2 ? inf : 0);
2. привести одну окружность в (0;0)

Углы

atan2 не нужон, вот мемы-то

спойлер - нужон. Не нужен, если нужно сравнить углы

можно смотреть точку на принадлежность многоугольнику бинпоиском а потом проверить на принадлежность треугольнику площадью треугольников

еее МВО

хотим построить многоугольник, который мво для набора точек

Саша делает это с Эндрю

Топ и Бот

сортим точки по полярному углу

в топ и бот пихаем первую точку

ифаем последнюю точку - это важно

пихаем точки в соответствующие векторы - верх и низ

а дальше грэхем делает все за нас

Тут оказалось, что писать стек можно и нужно на векторе, кек.