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

17387번: 선분 교차 2

문제 요약

문제

2차원 좌표 평면 위의 두 선분 L1, L2가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자. 한 선분의 끝 점이 다른 선분이나 끝 점 위에 있는 것도 교차하는 것이다.

L1의 양 끝 점은 (x1, y1), (x2, y2), L2의 양 끝 점은 (x3, y3), (x4, y4)이다.

사용 알고리즘

기하학

입출력

• 입력: 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다.
• 출력: L1과 L2가 교차하면 1, 아니면 0을 출력한다. ``` 예제1

입력 1 1 5 5 1 5 5 1 출력 1

## 풀이
CCW 를 활용하는 문제이다. 한 선분에서 다른 두개의 점이 각각 시계방향과 반시계방향으로 나눠져 있으면 그 선분을 교차한다. 이는 반대쪽에서도 만족해야 성립한다

## 어려웠던 점


## 배운 점 / 느낀 점


## 전체 코드
```cpp
#include <iostream>
#include <algorithm>
using namespace std;

struct Point {
    int x, y;
};

int ccw(Point a, Point b, Point c) {
    long long val = 1LL * (b.x - a.x) * (c.y - a.y) 
                  - 1LL * (b.y - a.y) * (c.x - a.x);
    if (val > 0) return 1;     // 반시계 방향
    if (val < 0) return -1;    // 시계 방향
    return 0;                  // 일직선
}

bool isCross(Point a, Point b, Point c, Point d) {
    int ab = ccw(a, b, c) * ccw(a, b, d);
    int cd = ccw(c, d, a) * ccw(c, d, b);

    if (ab == 0 && cd == 0) {
        // 두 선분이 일직선상에 있을 때는 범위 겹침 여부로 판단
        if (a.x > b.x) swap(a, b);
        if (c.x > d.x) swap(c, d);
        return !(b.x < c.x || d.x < a.x || max(a.y, b.y) < min(c.y, d.y) || max(c.y, d.y) < min(a.y, b.y));
    }

    return ab <= 0 && cd <= 0;
}

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

    Point A, B, C, D;
    cin >> A.x >> A.y >> B.x >> B.y;
    cin >> C.x >> C.y >> D.x >> D.y;

    cout << (isCross(A, B, C, D) ? 1 : 0);
    return 0;
}