Geometry/Polygon/137.cpp
/*
 * retorna true se o segmento de reta p1q1 intersecta
 * o segmento de reta p2q2
 */
retorna true se o segmento de reta p1q1 intersecta
o segmento de reta p2q2
retorna true se o segmento de reta p1q1 intersecta o segmento de reta p2q2
bool doIntersect(point p1, point q1, point p2, point q2) {
    double o1 = cross2(toVec(p1, q1), toVec(p1, p2));
    double o2 = cross2(toVec(p1, q1), toVec(p1, q2));
    double o3 = cross2(toVec(p2, q2), toVec(p2, p1));
    double o4 = cross2(toVec(p2, q2), toVec(p2, q1));
    if (o1 == 0 && onSegment(p1, q1, p2)) return true;
    if (o2 == 0 && onSegment(p1, q1, q2)) return true;
    if (o3 == 0 && onSegment(p2, q2, p1)) return true;
    if (o4 == 0 && onSegment(p2, q2, p1)) return true;
    if (o1 != o2 && o3 != o4 && o1 != 0 && o2 != 0 && o3 != 0 && o4 != 0) return true;
    return false; 
}
bool doIntersect ( point p1 , point q1 , point p2 , point q2 ) { double o1 = cross2 ( toVec ( p1 , q1 ) , toVec ( p1 , p2 ) ) ; double o2 = cross2 ( toVec ( p1 , q1 ) , toVec ( p1 , q2 ) ) ; double o3 = cross2 ( toVec ( p2 , q2 ) , toVec ( p2 , p1 ) ) ; double o4 = cross2 ( toVec ( p2 , q2 ) , toVec ( p2 , q1 ) ) ; if ( o1 == 0 && onSegment ( p1 , q1 , p2 ) ) return true ; if ( o2 == 0 && onSegment ( p1 , q1 , q2 ) ) return true ; if ( o3 == 0 && onSegment ( p2 , q2 , p1 ) ) return true ; if ( o4 == 0 && onSegment ( p2 , q2 , p1 ) ) return true ; if ( o1 != o2 && o3 != o4 && o1 != 0 && o2 != 0 && o3 != 0 && o4 != 0 ) return true ; return false ; }
retorna true se o segmento de reta p1q1 intersecta
 o segmento de reta p2q2
retorna true se o segmento de reta p1q1 intersecta o segmento de reta p2q2
// Casos especiais // p1, q1 e p2 são colineares e p2 repousa no segmento p1q1 // p1, q1 e q2 são colineares e q2 repousa no segmento p1q1 // p2, q2 e p1 são colineares e p1 repousa no segmento p2q2 // p2, q2 e q1 são colineares e q1 repousa no segmento p2q2 // Caso geral // não existe intersecção