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).