[백준][C++] 17387번: 선분 교차 2 <218>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

 

17387번: 선분 교차 2

생각의 흐름

우선 vector의 외적에 대한 지식이 없다면 다음글을 먼저 읽어보길 권장한다.

https://degurii.tistory.com/47

[알고리즘] CCW로 세 점의 방향성 판별하기

 

CCW의 개념을 알게 되었다면, 이를 활용하면 된다.

결론부터 말하면 CCW(A, B, C) < 0 && CCW(A, B, D) < 0 일때 선분이 교차할 수 있으며

CCW(A, B, C) == 0 || CCW(A, B, D) == 0 일때 세 점이 한 직선상에 위치힐 수 있다.

CCW(A, B, C) == 0 && CCW(A, B, D) == 0 일때 네 점이 일직선상에 위치할 수 있다.

 

소제목 입력

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int ccw(pair<ll, ll> p1, pair<ll, ll> p2, pair<ll, ll> p3) {
    ll temp = p1.first * p2.second + p2.first * p3.second + p3.first * p1.second;
    temp = temp - p1.second * p2.first - p2.second * p3.first - p3.second * p1.first;
    if(temp > 0) return 1;
    else if(temp == 0) return 0;
    else if(temp < 0) return -1;
}

bool isOverlapped(pair<ll, ll> A, pair<ll, ll> B, pair<ll, ll> C, pair<ll, ll> D) {
    int ans1 = ccw(A, B, C) * ccw(A, B, D);
    int ans2 = ccw(C, D, A) * ccw(C, D, B);

    if(ans1 == 0 && ans2 == 0) {
        if (A > B)swap(A, B);
        if (C > D)swap(C, D);

        if (A <= D && C <= B){
            return true;
        }else{
            return false;
        }
    }else if(ans1 <= 0 && ans2 <= 0) {
        return true;
    }else {
        return false;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    pair<ll, ll> A;
    pair<ll, ll> B;
    pair<ll, ll> C;
    pair<ll, ll> D;
    cin >> A.first >> A.second;
    cin >> B.first >> B.second;
    cin >> C.first >> C.second;
    cin >> D.first >> D.second;

    if(isOverlapped(A, B, C, D)) {
        cout << 1;
    }else{
        cout << 0;
    }

    return 0;
}