Как найти точку пересечения двух прямых, заданных парами точек?

Удобнее всего через косые произведения. Пусть прямые заданы точками A,B и C,D. Параметризуем первую прямую как A + t*(B-A). Тогда:

// возвращает true и точку пересечения; false если прямые параллельны
bool lineInter(const P& a, const P& b, const P& c, const P& d, pair<double,double>& res) {
    long long d1 = (b - a).cross(d - c); // знаменатель
    if (d1 == 0) return false;           // параллельны (или совпадают)
    long long t_num = (c - a).cross(d - c);
    double t = (double)t_num / d1;
    res = { a.x + t * (b.x - a.x), a.y + t * (b.y - a.y) };
    return true;
}

Идея: знаменатель (B-A) × (D-C) равен нулю ровно когда направляющие векторы прямых коллинеарны, то есть прямые параллельны. Если он не ноль, параметр t находится одним делением, и точка пересечения — линейная комбинация.

Числитель и знаменатель считаются в long long точно; деление переводит в double только в самом конце. Сложность O(1). Если нужна точная рациональная точка — храни числитель и знаменатель отдельно и не делай деление вовсе.