Большие координаты: где кончается 64 бита

Все геометрические предикаты - это произведения координат. Значит первый вопрос при координатах до $10^9$: помещается ли результат в целочисленный тип.

Три величины и три оценки

величина	при координатах до $C$	при $C = 10^9$
произведение координат $xy$	$C^2$	$10^{18}$
косое произведение разностей	$2(2C)^2 = 8C^2$	$8 \cdot 10^{18}$
удвоенная площадь многоугольника	$2(2C)^2 = 8C^2$	$8 \cdot 10^{18}$

Граница знакового 64-битного типа - $9{,}22 \cdot 10^{18}$. То есть при $C = 10^9$ всё три величины умещаются, но запас составляет всего 13%.

Замер на предельных многоугольниках подтверждает оценку: у квадрата во весь диапазон удвоенная площадь равна ровно $8 \cdot 10^{18}$ - это 86,7% от границы long long. У круга радиуса $10^9$ - $6{,}28 \cdot 10^{18}$, то есть 68%.

Что переполняется наверняка

int - на первом же слагаемом: $10^{18}$ против границы $2{,}1 \cdot 10^9$. Причём молча: программа не падает, а печатает правдоподобное число.

Отсюда практическое правило: в геометрии int не используется вовсе, даже когда координаты маленькие. Цена - лишний байт памяти, польза - отсутствие целого класса ошибок.

Когда 64 бит действительно мало

ситуация	почему
координаты до $10^{18}$ (например, после сложения)	уже произведение не помещается
сравнение расстояний как $d_1^2$ против $d_2^2$ при больших координатах	квадраты складываются, растёт вдвое
площадь считается без модуля и накапливается по многим фигурам	сумма не ограничена одной фигурой

Лекарство - __int128: он есть в GCC, арифметика в нём медленнее раза в два-три, зато границы хватает до $1{,}7 \cdot 10^{38}$. Печатать его напрямую нельзя, но для предикатов печатать и не нужно - достаточно знака.

using i128 = __int128;
int sign(i128 v) { return v > 0 ? 1 : v < 0 ? -1 : 0; }
i128 area2 = (i128)(b.x - a.x) * (c.y - a.y) - (i128)(b.y - a.y) * (c.x - a.x);

Как оценивать быстро

Считайте показатели: координаты $10^k$ дают произведения $10^{2k}$, косые произведения - $10^{2k+1}$ с небольшим множителем. Дальше сравнивайте с $9 \cdot 10^{18}$.

Если получилось «впритык», как здесь, - это повод не расслабляться, а проверить оценку на предельном тесте: квадрат во весь диапазон обычно и есть худший случай.

Смежное

• Точность и эпсилон;
• Площадь многоугольника.