[Gold II] 선분 교차 2 - 17387

문제 링크

성능 요약

메모리: 2020 KB, 시간: 0 ms

분류

많은 조건 분기, 기하학, 선분 교차 판정

제출 일자

2024년 3월 9일 13:21:14

문제 설명

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을 출력한다.

🙇‍♀️풀이

나는 멍청이

CCW (Conter Clockwise) 알고리즘을 이용하는 문제이다.

ccw 알고리즘을 처음 알아서 알고리즘부터 공부했다.

벡터 외적을 통해서 방향성을 알수 있으니 두 선분의 형태를 알 수 있는 알고리즘이다.

공부하고 이해했다고 생각해서 코드를 짰는데 무한 실패로 인해 블로그를 참조했다.

아니 너무 억울한게.. 내 실력이긴 하지만 아.. 왜 틀림.. 맞왜틀..

#include <iostream>

using namespace std;

struct P {
    long long x, y;
    bool operator<=(P const& p1) {
        if (x == p1.x) {
            return y <= p1.y;
        }
        return x <= p1.x;
    }
};

struct Line {
    P p1, p2;
};

Line line[2];

int CCW(const P& p1, const P& p2, const P& p3) {
    long long res = (p1.x * p2.y + p2.x * p3.y + p3.x * p1.y) - \
        (p2.x * p1.y + p3.x * p2.y + p1.x * p3.y);

    // 행렬식을 통해서 구하기
    // int determinant = (p2.x*p3.y - p2.y*p3.x) - \
    //                   (p1.x*p3.y - p1.y*p3.x) + \
    //                   (p1.x*p2.y - p1.y*p2.x);

    if (res > 0) return 1;   //반시계
    else if (res < 0) return -1;     //시계
    else return 0;
}

bool isline_intersect(Line& l1, Line& l2) {
    int std1, std2;

    std1 = CCW(l1.p1, l1.p2, l2.p1) * CCW(l1.p1, l1.p2, l2.p2);
    std2 = CCW(l2.p1, l2.p2, l1.p1) * CCW(l2.p1, l2.p2, l1.p2);

    if (std1 <= 0 && std2 <= 0) {
        if (std1 == 0 && std2 == 0) {     //선분이 일직선인 경우
            if (l1.p2 <= l1.p1) swap(l1.p1, l1.p2);
            if (l2.p2 <= l2.p1) swap(l2.p1, l2.p2);

            return l1.p1 <= l2.p2 && l2.p1 <= l1.p2;
        }
        else return true;   //일직선이 아니면 교차함
    }
    else return false;  //CCW가 같은 방향이 있으면 
}

void solve() {
    if (isline_intersect(line[0], line[1])) {
        cout << 1;
    }
    else cout << 0;
}

void input() {
    long long x1, x2, y1, y2;
    P p1, p2;
    for (int i = 0; i < 2; i++) {
        cin >> p1.x >> p1.y >> p2.x >> p2.y;
        line[i].p1 = p1;
        line[i].p2 = p2;
    }
}

int main() {

    input();
    solve();

    return 0;
}

코드 다시 보면서 복기해야겠다.

복기가 어느정도 되면 선분교차 1, 3은 보지않고 할 예정이다.

멘탈에 금갔어..

image

참고