Главные правила работы с геометрией

При работе с геометрией есть три главных правила. (Этот текст — в дополнение в основной теории в видеолекциях.)

Во-первых, помните правила работы с вещественными числами, и главное — не используйте вещественные числа, если можно обойтись без них. Если все входные данные у вас целочисленны (а так обычно бывает), то нередко можно все задачу полностью решить в целых числах. И это намного правильнее, чем использовать вещественные числа. Иногда, конечно, бывает так, что в целых числах задачу не решить, например, если ответ сам по себе может быть вещественным (например, если надо найти точку пересечения двух прямых, то ее координаты могут быть нецелыми, даже если входные данные целочисленны). Но тогда постарайтесь в любом случае использовать вещественные числа только там, где они потребовались — например, прежде чем искать точку пересечения вы, наверное, заходите проверить, не параллельны ли две прямые, а это можно и нужно делать полностью в целых числах. А если уж вам приходится использовать вещественные числа, то не забывайте про eps.

Во-вторых, ваши друзья — это векторное и скалярное произведение. Почти все задачи про прямые, отрезки, точки и т.д. можно решить с помощью векторных и скалярных произведений, и такое решение будет работать чище и надежнее, чем любое другое. Если вы работаете с прямыми, то можете использовать представление прямой в виде коэффициентов A, B, C — это по сути то же векторное или скалярное произведение, только вид сбоку.

В-третьих, старайтесь не работать отдельно с координатами X и Y. Если вы хотите рассмотреть особо случай типа x==0, или вообще вы хотите написать формулу, в которую входит только x, и т.п. — скорее всего, вы что-то делаете не так. Скорее вам надо использовать векторное или скалярное произведение (см. правило 2), и x==0 не будет особым случаем. Вообще, большинство из тех задач, которые будут в этой теме, обладают вращательной симметрией — если вы повернете всю картину на произвольный угол вокруг начала координат, то задача останется такой же, ответ или не изменится, или тоже повернется. Поэтому логично и в коде использовать только те величины, которые не меняются при повороте. Вот скалярное и векторное произведения — не меняются. А отдельные координаты — меняются. Если вы пишете условие if x == 0, то при повороте результат сравнения изменится. А если вы считаете векторное произведение и сравниваете его с нулем — результат сравнения не изменится. Намного удобнее писать код так, чтобы он не зависел от поворота. (Конечно, если по смыслу задачи вращательной симметрии нет, то основные аргументы тут уже не работают, и вам где-то придется писать несимметричный код, но во многих задачах симметрия есть.)

Частным случаем п. 3 является то, что не надо использовать представление прямой в виде y=k*x+b. Мало того, что оно не симметрично относительно X и Y, оно еще и не работает для вертикальных прямых. Используйте представление в виде A*x+B*y+C=0, или через векторное произведение (что на самом деле то же самое, что и ABC), или параметрический способ.