벡터의 외적 아는사람?
반시계방향(CCW)으로 외적하면 양수, 시계방향으로 외적하면 음수, 일직선이면 0
이걸로 선분의 교차 여부를 알 수 있다. 어떻게??
p1(x1, y1) p2(x2, y2) / p3(x3, y3) p4(x4, y4) 이렇게 선분 두개가 있을 때 ccw(p1, p2, p3) * ccw(p1, p2, p4)의 값과 ccw(p3, p4, p1) * ccw(p3, p4, p2)의 값 둘 중 하나라도 1이면 선분은 교차하지 않는다.
그런데 예외가 있다. 바로 점 4개가 일직선상에 위치할때다. (1, 1) (2,2) / (3, 3) (4, 4) 이 두 선분은 교차하지 않지만 ccw를 계산해서 곱한 값이 모두 0이다.
대소관계를 비교하기 위해 p1, p3에 작은 값이 들어가도록 swap을 하고 가운데 겹치는 부분이 있는지 확인해서 교차 여부를 알아내도록 하자.
#include <bits/stdc++.h>
using namespace std;
int ccw(long long x1, long long y1, long long x2, long long y2, long long x3, long long y3) {
long long temp = x1*y2+x2*y3+x3*y1;
temp = temp - y1*x2-y2*x3-y3*x1;
if (temp > 0) {
return 1;
}
else if (temp < 0) {
return -1;
}
else {
return 0;
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
long long x1, y1, x2, y2, x3, y3, x4, y4;
cin >> x1 >> y1 >> x2 >> y2;
cin >> x3 >> y3 >> x4 >> y4;
int ccw1 = ccw(x1, y1, x2, y2, x3, y3);
int ccw2 = ccw(x1, y1, x2, y2, x4, y4);
int ccw3 = ccw(x3, y3, x4, y4, x1, y1);
int ccw4 = ccw(x3, y3, x4, y4, x2, y2);
pair<long long, long long> p1 = {x1, y1};
pair<long long, long long> p2 = {x2, y2};
pair<long long, long long> p3 = {x3, y3};
pair<long long, long long> p4 = {x4, y4};
bool s1 = (ccw1*ccw2<=0);
bool s2 = (ccw3*ccw4<=0);
if (ccw1*ccw2 == 0 && ccw3*ccw4 == 0) {
if (p1 > p2) {
swap(p1, p2);
}
if (p3 > p4) {
swap(p3, p4);
}
if (p2 < p3 || p1 > p4) {
s1 = false;
}
}
cout << (s1&&s2);
return 0;
}
살면서 처음으로 기하 문제를 풀어봤다. 신경쓸게 매우매우매우 많았다. 순서, 오버플로우 조심!
점 대소관계 비교할 때 x값이 같은 경우 y값으로 비교해야하기 때문에 그냥 pair에 집어넣어서 자동으로 비교되게 했다.
정답률이 점점 하늘나라로 떠나고있다.