백준 12781 PIZZA ALVOLOC

안유태·2023년 7월 12일
0

알고리즘

목록 보기
109/239

12781번: PIZZA ALVOLOC

선분 교차 판정을 이용한 문제이다. 선분 교차를 확인하는 법은 ccw를 이용한다. 한 점을 기준으로 다른 두점과의 직선 방향을 ccw를 이용해 구했을 때 서로 방향이 다르다면 선분이 교차함을 의미한다. 원래는 추가로 다른 한 점을 기준으로 선분 교차 확인을 한번 더 해야하는데 이 문제에서는 다각형 위의 좌표들이 주어지기 때문에 한번만 확인을 해주면 된다. 오랜만에 ccw 문제라 많이 햇갈렸었다.



#include <iostream>

using namespace std;

int ax, bx, cx, dx, ay, by, cy, dy;

void solution() {
    int result = 1;

    int a = (bx - ax) * (cy - ay) - (cx - ax) * (by - ay);
    int b = (bx - ax) * (dy - ay) - (dx - ax) * (by - ay);

    if (!(a < 0 && b > 0) && !(a > 0 && b < 0)) {
        result = 0;
    }

    int c = (cx - dx) * (ay - dy) - (ax - dx) * (cy - dy);
    int d = (cx - dx) * (by - dy) - (bx - dx) * (cy - dy);

    if (!(c < 0 && d > 0) && !(c > 0 && d < 0)) {
        result = 0;
    }

    cout << result;
}

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

    cin >> ax >> ay >> bx >> by >> cx >> cy >> dx >> dy;

    solution();

    return 0;
}
profile
공부하는 개발자

0개의 댓글