선분 교차 판정을 이용한 문제이다. 선분 교차를 확인하는 법은 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;
}