[ 백준 ] 17387번 - 선분 교차 2 (C++)

https://www.acmicpc.net/problem/17387

17387번: 선분 교차 2

 

[ 문제풀이 ]

 

선분이 교차할 때의 조건을 알아야 풀 수 있는 문제입니다.

 

 

위와 같이 2개의 선분을 서로 교차한다고 말합니다. 이때 p1과 p2를 이은 선분을 벡터 v1이라고 하면 v1 = p2 - p1이 됩니다. 이와 같은 원리로 v2 = p3 - p1, v3 = p4 - p1이라고 하면 다음과 같이 나타낼 수 있습니다.

 

 

이때 v1과 v2를 외적 하면 반시계 방향이므로 양수가 나오고, 반대로 v1과 v3를 외적 하면 시계방향이므로 음수가 나옵니다. 위 결과로 보아 벡터들의 외적 값을 구하고 그 방향이 반대라면 선분이 교차한다고 표현할 수 있습니다.

 

 

하지만 위와 같은 상황에서는 조건을 만족하지만 교차한다고 표현할 수 없습니다.

 

이 때에는 또 다른 벡터를 이용해서 구해줍니다. 즉, v4 = p4 - p3, v5 = p2 - p3, v6 = p1 = p3일 때 v4를 기준으로 모두 같은 방향에 있기 때문에 조건을 만족하지 않습니다.

 

 

따라서 ccw(p1, p2, p3) * ccw(p1, p2, p4) < 0 && ccw(p3, p4, p1) * ccw(p3, p4, p2) < 0이 되어야 합니다.

 

다른 예외 사항도 몇 가지가 있습니다.

 

3개의 점이 한 직선상에 있거나 4개의 점이 한 직선상에 있는 경우입니다.

 

 

위와 같은 경우 p1, p2, p3가 같은 직선상에 있고, ccw(p1, p2, p3)는 0이 나오게 됩니다.

 

즉, ccw(p1, p2, p3) * ccw(p1, p2, p4) == 0 && ccw(p3, p4, p1) * ccw(p3, p4, p2) < 0 이거나,

ccw(p1, p2, p3) * ccw(p1, p2, p4) < 0 && ccw(p3, p4, p1) * ccw(p3, p4, p2) == 0을

 

 

마지막으로 위와 같은 상황에서는 모든 ccw가 0이므로 다른 조건으로 교차 여부를 판단해야 합니다. 한 직선을 기준으로 p1 < p2와 p3 < p4를 만족한다면 p2 > p3와 p4 > p1을 만족한다면 교차한다고 표현할 수 있습니다.

 

[ 소스 코드 ]

#include <iostream>
#include <algorithm>
 
using namespace std;
 
struct pos {
    long long x;
    long long y;
};
 
pos arr[4];
 
bool cmp(pos left, pos right)
{
    if(left.x == right.x) return left.y <= right.y;
    return left.x <= right.x;
}
 
int closs(pos p1, pos p2, pos p3) {         //외적을 통해 방향을 리턴
    long long cross_product = (p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y);
 
    if (cross_product > 0) {
        return 1;
    }
    else if (cross_product < 0) {
        return -1;
    }
    else {
        return 0;
    }
}
 
int main()
{
    for (int i = 0; i < 4; i++) {
        cin >> arr[i].x >> arr[i].y;
    }
 
    sort(arr, arr + 2, cmp);
    sort(arr + 2, arr + 4, cmp);
    int l1 = closs(arr[0], arr[1], arr[2]) * closs(arr[0], arr[1],arr[3]);
    int l2 = closs(arr[2], arr[3], arr[0]) * closs(arr[2], arr[3], arr[1]);
    if (l1 == 0 &&l2 == 0) {            //두 선이 일직선상에 있을 때
        if (cmp(arr[2], arr[1]) && cmp(arr[0], arr[3])) {
            cout << 1;
            return 0;
        }
    }
    else if (l1 <= 0 && l2 <= 0) {
        cout << 1;
        return 0;
    }
 
    cout << 0;
}