Verifique a interseção de dois segmentos

Você recebe dois segmentos $(a, b)$ e $(c, d)$. Você tem que verificar se eles se cruzam. Obviamente, você pode encontrar a interseção e verificar se ela não está vazia, mas isso não pode ser feito em números inteiros para segmentos com coordenadas inteiras. A abordagem descrita aqui pode funcionar em números inteiros.

Algoritmo

Primeiro, considere o caso em que os segmentos fazem parte da mesma linha. Nesse caso, é suficiente verificar se suas projeções sobre $Ox$ e $Oy$ se cruzam. No outro caso, $a$ e $b$ não devem estar no mesmo lado da linha $(c, d)$, e $c$ e $d$ não devem estar no mesmo lado da linha $(a, b)$. Pode ser verificado com alguns produtos vetoriais.

Implementação

O algoritmo fornecido é implementado para inteiros. Obviamente, pode ser facilmente modificado para trabalhar com doubles.

struct pt {
    long long x, y;
    pt() {}
    pt(long long _x, long long _y) : x(_x), y(_y) {}
    pt operator-(const pt& p) const { return pt(x - p.x, y - p.y); }
    long long cross(const pt& p) const { return x * p.y - y * p.x; }
    long long cross(const pt& a, const pt& b) const { return (a - *this).cross(b - *this); }
};

int sgn(const long long& x) { return x >= 0 ? x ? 1 : 0 : -1; }

bool inter1(long long a, long long b, long long c, long long d) {
    if (a > b)
        swap(a, b);
    if (c > d)
        swap(c, d);
    return max(a, c) <= min(b, d);
}

bool check_inter(const pt& a, const pt& b, const pt& c, const pt& d) {
    if (c.cross(a, d) == 0 && c.cross(b, d) == 0)
        return inter1(a.x, b.x, c.x, d.x) && inter1(a.y, b.y, c.y, d.y);
    return sgn(a.cross(b, c)) != sgn(a.cross(b, d)) &&
           sgn(c.cross(d, a)) != sgn(c.cross(d, b));
}