본문 바로가기

백준 문제풀이

BOJ 17387 선분 교차 2 [C++]

까다롭고 복잡한 문제다.

 

 

그리고 문제를 푸는 핵심 개념이 ccw라는 것인데 함수에 이런 값을 넣으면 이렇게 튀어나오는구나 정도만 이해했지

공식 내용은 이해하지 못했다. 그래서 선형대수학 공부를 좀 하려한다.

 

아무튼 ccw함수는 (2차원이라 가정) 세점 p1, p2, p3를 입력받으면 p1, p2, p3로 가는 경로가

시계방향이면 -1, 반시계는 1, 직선이면 0 을 반환하는 함수다.

 

이것을 4번하고 곱하고 비교해서 두 직선이 평행하지 않을때 교차 여부는

입력된 4개의 좌표의 값들을 ccw만 돌리고 직접 대소비교하지 않고도 쉽게 판단할 수 있다.

 

하지만 평행할때는 좀 까다롭다.

내가 놓쳐서 헤맸던 가장 큰 것이 입력시 x1 < x2,  x3 < x4,  y1 < y2,  y3 < y4가 보장되지 않는다는 것이다.

그래서 두 값중 큰것, 작은것을 max, min함수로 구해 비교한다. ()

 

아래는 최종 코드다

#include <bits/stdc++.h>


using namespace std;
typedef long long int lld;


int ccw(lld x1, lld x2, lld x3, lld y1, lld y2, lld y3) {
    lld res = (x2 - x1)* (y3 - y1) - (y2 - y1) * (x3 - x1);
    
    if (res > 0) return 1;
    else if (res < 0) return -1;
    else return 0;
}

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

    lld a, b, c, d, p, q, r, s;
    cin >> a >> p >> b >> q;
    cin >> c >> r >> d >> s;

    int l12 = ccw(a, b, c, p, q, r) * ccw(a, b, d, p, q, s);
    int l21 = ccw(c, d, a, r, s, p) * ccw(c, d, b, r, s, q);

    if (l12 == 0 && l21==0) {
        if (max(a,b) < min(c,d) || max(c,d) < min(a,b)) cout << 0;
        else if (max(p,q) < min(r,s) || max(r, s) < min(p, q)) cout << 0;
        else cout << 1;
    }
    else if (l12 <= 0 && l21 <= 0) cout << 1;
    else cout << 0;

    return 0;

}

'백준 문제풀이' 카테고리의 다른 글

BOJ 3665 최종 순위 [C++]  (0) 2024.03.19
BOJ 16566 카드 게임 [C++]  (1) 2024.03.16
BOJ 9328 열쇠 [C++]  (0) 2024.02.26
BOJ 1918 후위 표기식 [C++]  (1) 2024.02.14
BOJ 9663 N-queen [C++]  (0) 2024.02.13