(백준(BOJ)) 선분교차점2 (#17387)_C++

선분이 교차하면 예상보다 더 많은 모양이 있습니다.

위 그림의 경우를 대략적으로 상상할 수 있습니다.

그렇다면 그들이 교차하는지 어떻게 알 수 있습니까?

ccw를 사용하시면 됩니다 (모르시면 공부해봅시다)

위의 그림에서 (a)를 예로 들어 보겠습니다.

점 C와 B는 선분 AB에 대해 서로 다른 방향에 있으면 교차하는 것으로 간주할 수 있습니다.

이것은 (벡터 AB와 벡터 AC의 외적)과 (벡터 AB와 벡터 AD의 외적)으로 쉽게 결정할 수 있습니다.

외부 값은 크게 세 가지 범주로 나눌 수 있습니다.

-1 : 반시계방향

0 : 직선으로

1 : 시계방향

두 외적의 곱이 0보다 작거나 같으면 교차하는 것으로 간주됩니다.

그러나 AB 선분만 체크하면 (f)와 같은 예외가 발생할 수 있습니다.

따라서 선분 AB와 선분 CD를 모두 확인해야 합니다.

그러면 직선 위에 있는 경우를 제외하고 두 직선을 ​​구분할 수 있습니다.

두 개의 선분이 직선 위에 있는 경우는 선분 AB의 외적과 선분 CD의 외적의 곱이 모두 0일 때입니다.

이 경우 두 세그먼트의 두 끝점 위치를 비교할 수 있습니다.

비교에서 겹치는 부분이 있으면 교차합니다.

---

답변

#include <iostream>

using namespace std;

struct line{
    pair<int, int> p1;
    pair<int, int> p2;
};

line l1, l2;

int ccw(pair<int, int> a, pair<int, int> b, pair<int, int> c){
    pair<int, int> v = {b.first - a.first, b.second - a.second};
    pair<int, int> u = {c.first - a.first, c.second - a.second};

    long long result = (long long)v.first * u.second - (long long)u.first * v.second;

    if (result > 0)
        return 1;
    else if (result == 0)
        return 0;
    else
        return -1;
}

bool cross_check(){
    //각 선분에 대한 방향
    int check_l1 = ccw(l1.p1, l1.p2, l2.p1) * ccw(l1.p1, l1.p2, l2.p2);
    int check_l2 = ccw(l2.p1, l2.p2, l1.p1) * ccw(l2.p1, l2.p2, l1.p2);

    //두 선분이 일직선 상에 존재하는 경우
    if (check_l1 == 0 && check_l2 == 0){
        //좌하단에 있는 점을 첫번째점으로 변경
        if (l1.p1 > l1.p2)
            swap(l1.p1, l1.p2);
        if (l2.p1 > l2.p2)
            swap(l2.p1, l2.p2);

        //두 선분이 겹쳐지는 경우
        if (l1.p1 <= l2.p2 && l1.p2 >= l2.p1)
            return true;
        else
            return false;
    }

    //두 선분이 한 점에서 만나는 경우
    if (check_l1 <= 0 && check_l2 <= 0)
        return true;
    //교차하지 않는 경우
    else
        return false;
}

int main(){
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);

    //input
    cin >> l1.p1.first >> l1.p1.second >> l1.p2.first >> l1.p2.second;
    cin >> l2.p1.first >> l2.p1.second >> l2.p2.first >> l2.p2.second;

    //check and output
    if (cross_check() == true)
        cout << 1;
    else
        cout << 0;
}