문제에 대한 첫인상

최근 geometry 문제들에 대한 경험치를 높이기 위해서 관련 문제들을 열심히 풀어보고 있다. 이번에 풀어볼 문제는 “두 선분이 주어졌을 때, 서로 교차하는지 아닌지 판단”하는 문제였다. 17386번 문제의 경우 “세 점이 일직선 위에 있는” 경우는 없으므로 상대적 방향만 고려해주면 쉽게 구할 수 있었다.

공간 상에서의 선분의 관계를 구할 때에 기울기를 이용하는 방법도 있겠지만, 외적을 활용하면 더욱 편하게 풀 수 있다. 외적의 부호를 비교하면 두 벡터가 반시계/시계/일직선 상에 위치하는지 확인할 수 있다.

문제에서 선분 L1의 두 점을 A, B, 선분 L2의 두 점을 C, D라고 해보자. 그러면 AB벡터를 기준으로 AC벡터, AD벡터와 비교했을 때에 (AB-AC) (AB-AD)의 방향이 서로 달라야 교차할 가능성이 있다. 하지만 이 경우 실제로 선분을 그었을 때에는 떨어진 경우가 있으므로 C점을 기준으로 다시 비교해주어야 교차하는지를 완전히 알아낼 수 있다.

#include <iostream>

using namespace std;

long long ccw(long long x1, long long y1, long long x2, long long y2, long long x3, long long y3){
    long long temp = (x2-x1)*(y3-y1) - (y2-y1)*(x3-x1);
    if (temp > 0){
        return 1; // 반시계 방향
    } else if (temp < 0){
        return -1; // 시계 방향
    } else{
        return 0; // 일직선
    }
}

int main()
{
    long long x1, y1, x2, y2, x3, y3, x4, y4;
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
    bool ccw2 = ccw(x1, y1, x2, y2, x3, y3)*ccw(x1, y1, x2, y2, x4, y4) < 0;
    bool ccw3 = ccw(x3, y3, x4, y4, x1, y1)*ccw(x3, y3, x4, y4, x2, y2) < 0;
    if (ccw2 && ccw3){
        cout << 1; 
    } else{
        cout << 0;
    }
    
    return 0;
}