Producto cruz y orientación

Tema: Geometría · temarios: Syllabus OCI · Syllabus IOI

📍 Para profundizar: esta ficha amplía las clases de la Ruta de Aprendizaje. Puedes estudiarla cuando un problema requiera esta herramienta.

Qué hace

El producto cruz indica si tres puntos giran a la izquierda, a la derecha o son colineales — base de casi toda la geometría entera.

Complejidad: O(1).

Cuándo usarlo

Orientación, área de triángulo/polígono, intersección de segmentos, convex hull. Úsalo con enteros para evitar errores de precisión.

Implementación recomendada (C++)

struct P { long long x, y; };
// cross > 0: O->A->B gira a la izquierda; < 0 derecha; = 0 colineales.
long long cross(const P& O, const P& A, const P& B) {
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}
int orient(const P& O, const P& A, const P& B) {
    long long c = cross(O, A, B);
    return (c > 0) - (c < 0);              // -1, 0, +1
}

⚠️ Notas

Mantente en enteros: con coordenadas hasta 10^9, el cruce llega a ~10^18, así que long long (o __int128 si multiplicas más).

🔗 Relacionados