[C++][백준 17387] 선분 교차 2

문제

접근 방법

CCW를 활용하면 된다.

CCW를 활용하면 방향을 확인할 수 있다.
한 선분을 기준으로 삼고 다른 선분의 점을 이용해서 방향을 구했을 때 교차해있다면 양수와 음수가 나와야 한다.

왜냐하면 시계방향에 한 개, 반시계 방향에 한 개 존재하기 때문이다.

코드

#include <iostream>
using namespace std;
using ll = long long;
struct point
{
    ll x, y;
} p1, p2, p3, p4;
int ccw(const point &a, const point &b, const point &c)
{
    ll ret = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
    if (ret < 0)
        return -1;
    else if (ret > 0)
        return 1;
    else
        return 0;
}
bool isLine(int a, int b, int c, int d)
{
    if (a > b) // b가 더 크게
    {
        swap(a, b);
    }
    if (c > d) // d가 더 크게
    {
        swap(c, d);
    }
    return (a <= d && b >= c) || (c <= b && d >= a); // 좌표의 대소 관계 확인
}
bool isCross()
{
    // ccw 구하기
    int z1 = ccw(p1, p2, p3);
    int z2 = ccw(p1, p2, p4);
    int z3 = ccw(p3, p4, p1);
    int z4 = ccw(p3, p4, p2);

    if (z1 * z2 == 0 && z3 * z4 == 0) // 같은 선상에 있는 경우
    {
        return isLine(p1.x, p2.x, p3.x, p4.x) && isLine(p1.y, p2.y, p3.y, p4.y);
    }

    return z1 * z2 <= 0 && z3 * z4 <= 0;
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> p1.x >> p1.y >> p2.x >> p2.y >> p3.x >> p3.y >> p4.x >> p4.y;
    cout << isCross();
    return 0;
}

풀이

이런 식으로 떨어진 경우에는 한 선분을 기준으론 서로 다른 방향이겠지만 다른 한 선분을 기준으론 한 방향에 몰려있다.
그렇기에 두 선분 모두 CCW의 곱을 구해주어야 한다.

한 선분의 끝 점이 다른 선분이나 끝 점 위에 있는 것도 교차하는 것이다.

해당 조건을 위해 0인 경우도 허용해야 한다.
이렇게 겹치는 경우를 확인할 때는 두 선분의 좌표를 비교하여서 겹치는지 확인해 주면 된다.