선분 교차 2

백준 17387번: 선분 교차 2

아이디어

벡터의 외적 아는사람?
반시계방향(CCW)으로 외적하면 양수, 시계방향으로 외적하면 음수, 일직선이면 0

이걸로 선분의 교차 여부를 알 수 있다. 어떻게??

p1(x1, y1) p2(x2, y2) / p3(x3, y3) p4(x4, y4) 이렇게 선분 두개가 있을 때 ccw(p1, p2, p3) * ccw(p1, p2, p4)의 값과 ccw(p3, p4, p1) * ccw(p3, p4, p2)의 값 둘 중 하나라도 1이면 선분은 교차하지 않는다.

그런데 예외가 있다. 바로 점 4개가 일직선상에 위치할때다. (1, 1) (2,2) / (3, 3) (4, 4) 이 두 선분은 교차하지 않지만 ccw를 계산해서 곱한 값이 모두 0이다.

대소관계를 비교하기 위해 p1, p3에 작은 값이 들어가도록 swap을 하고 가운데 겹치는 부분이 있는지 확인해서 교차 여부를 알아내도록 하자.

코드

#include <bits/stdc++.h>

using namespace std;

int ccw(long long x1, long long y1, long long x2, long long y2, long long x3, long long y3) {
    long long temp = x1*y2+x2*y3+x3*y1;
    temp = temp - y1*x2-y2*x3-y3*x1;
    if (temp > 0) {
        return 1;
    } 
    else if (temp < 0) {
        return -1;
    } 
    else {
        return 0;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    long long x1, y1, x2, y2, x3, y3, x4, y4;
    cin >> x1 >> y1 >> x2 >> y2;
    cin >> x3 >> y3 >> x4 >> y4;
    
    int ccw1 = ccw(x1, y1, x2, y2, x3, y3);
    int ccw2 = ccw(x1, y1, x2, y2, x4, y4);
    int ccw3 = ccw(x3, y3, x4, y4, x1, y1);
    int ccw4 = ccw(x3, y3, x4, y4, x2, y2);
    
    pair<long long, long long> p1 = {x1, y1};
    pair<long long, long long> p2 = {x2, y2};
    pair<long long, long long> p3 = {x3, y3};
    pair<long long, long long> p4 = {x4, y4};
    
    bool s1 = (ccw1*ccw2<=0);
    bool s2 = (ccw3*ccw4<=0);
        
    if (ccw1*ccw2 == 0 && ccw3*ccw4 == 0) {
        if (p1 > p2) {
            swap(p1, p2);
        }
        if (p3 > p4) {
            swap(p3, p4);
        }
        if (p2 < p3 || p1 > p4) {
            s1 = false;
        }
    }
    cout << (s1&&s2);
    return 0;
}

여담

살면서 처음으로 기하 문제를 풀어봤다. 신경쓸게 매우매우매우 많았다. 순서, 오버플로우 조심!
점 대소관계 비교할 때 x값이 같은 경우 y값으로 비교해야하기 때문에 그냥 pair에 집어넣어서 자동으로 비교되게 했다.
정답률이 점점 하늘나라로 떠나고있다.