https://contest.ucup.ac/contest/4126/problem/20255
Не будем углубляться в детали задачи, но там, как и в любой задаче на вычгеом, нужно быть очень аккуратным с точностью вычислений. Существует несколько "школ" того, как правильно писать задачи на вычгеом. Некоторые люди спокойно создают структуру
Point с double x, y, добавляют в случайные места программы EPS при различных вычислениях и вообще ничего не бояться по жизни. Я же очень сильно боюсь так делать и стараюсь писать все вычисления в целых числах. Иначе, при получении WA, очень сложно понять это бага в коде или нужно просто поменять EPS.А еще большинство алгоритмов вычислительной геометрии выражаются через две операции — векторное и скалярное произведение. Например, всякие выпуклые оболочки, пересечения отрезков, проверки на нахождение внутри треугольника и так далее.
Существует много разных способов пересечь две прямых. Расскажу про тот, которым было удобно воспользоваться в данной задаче. Пусть одна прямая задана координатами двух точек
A и B лежащих на ней, а другая точками C и D. Нужно найти некоторую точку Q, которая лежит на их пересечении. Запишем позицию Q в виде A + u * (B - A). Удобно, что получив значение u, можно заодно понять где конкретно она лежит по отношению к A и B. Например, если 0 <= u <= 1, то она лежит на отрезке AB. Если u > 1, то на продолжении луча AB.Как найти
u? Мне кажется удобно думать об этом с геометрической точки зрения. Посмтрим на треугольники ADC и BCD. Их площади относятся как u к 1 - u. Площадь треугольника ADC это просто векторное произведение AD * AC (с точностью до 1/2). Отсюда получаем, что u = ADC / (BCD + ADC).Прикольный факт, что о площадях надо думать как о чем-то, у чего есть знак (и считается по формуле векторного произведения). Тогда эта формула для
u продолжает работать даже для u < 0 и u > 1, когда какие-то из площадей отрицательные. А если BCD + ADC = 0, то это обозначает, что AB и CD параллельны.В таком формате еще очень удобно думать про то, какой тип данных нужен для хранения всего этого. Если координаты были порядка
C = 10^9, то векторное произведение порядка C^2, а u это дробь, где числитель и знаменатель порядка C^2. Если мы захотим такие дроби сравнивать, то нужен будет тип, который вмещает C^4 (int128).