까다롭고 복잡한 문제다.
그리고 문제를 푸는 핵심 개념이 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 |