알고리즘
양 선분이 평행할 경우, 또는 한 쪽이 x축에 평행하고, 다른 축이 y축에 평행할 경우엔 조건문을 통해 범위를 잘 검사하여 처리
나머지 경우엔 다음과 같은 방법을 사용한다.
첫번째 선분을 이루는 직선이 두번째 선분을 양분하고, 그 반대도 양분하면 두 선분은 교차한다.
이때 한 직선이 한 선분을 양분하는지 알아보는 식은 다음과 같다.
f1 = (y21-y11)(x12-x11) - (x21-x11)(y12-y11)
f2 = (y22-y11)(x12-x11) - (x22-x11)(y12-y11)
이고, f1 * f2 < 0 일때 양분함.
이때, 이 문제에서는 끝 점에 지나는 것도 교차한다고 판단하니, f1 * f2 <= 0 일때 참으로 판단하자.
단, 이러면 평행할때도 0이 나오니, 평행 검사는 이 방법보다 먼저 하자.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
typedef long long ll;
using namespace std;
struct line {
ll h, t, ch, ct;
};
void swap(ll* a, ll* b) {
ll t = *a;
*a = *b;
*b = t;
}
void makeLine(line* l, ll x1, ll x2, ll y1, ll y2) {
ll b = x2 - x1, h = y2 - y1;
if (b < 0 && h < 0) {
b *= -1;
h *= -1;
}
ll ch = b * y1 - h * x1, ct = b;
*l = { h, b, ch, ct };
}
bool check(ll x1, ll x2, ll x3, ll y1, ll y2, ll y3) {
if ((((x3 >= x1 && x3 <= x2) && (y3 >= y1 && y3 <= y2))|| ((x3 <= x1 && x3 >= x2) && (y3 <= y1 && y3 >= y2))))
return true;
return false;
}
bool is_cross(ll x1, ll x2, ll x3, ll x4, ll y1, ll y2, ll y3, ll y4) {
ll f1 = ((y3 - y1) * (x2 - x1)) - ((x3 - x1) * (y2 - y1)), f2 = ((y4 - y1) * (x2 - x1)) - ((x4 - x1) * (y2 - y1));
if ((f1 <= 0 && f2 >= 0) || (f1 >= 0 && f2 <= 0))
return true;
return false;
}
bool solve() {
ll x1, x2, x3, x4, y1, y2, y3, y4;
cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
if (x1 > x2) {
swap(&x1, &x2);
swap(&y1, &y2);
}
if (x3 > x4) {
swap(&x3, &x4);
swap(&y3, &y4);
}
line l1, l2;
makeLine(&l1, x1, x2, y1, y2);
makeLine(&l2, x3, x4, y3, y4);
if (l1.h * l2.t == l1.t * l2.h) {
if (l1.ch * l2.ct == l1.ct * l2.ch && (check(x1, x2, x3, y1, y2, y3) || check(x1, x2, x4, y1, y2, y4) || check(x3, x4, x1, y3, y4, y1) || check(x3, x4, x2, y3, y4, y2)))
return 1;
return 0;
}
else if (l1.t == 0 && l2.h == 0) {
if (x1 >= x3 && x1 <= x4 && ((y3 >= y1 && y3 <= y2) || (y3 <= y1 && y3 >= y2)))
return 1;
return 0;
}
else if (l2.t == 0 && l1.h == 0) {
if (x3 >= x1 && x3 <= x2 && ((y1 >= y3 && y1 <= y4) || (y1 <= y3 && y1 >= y4)))
return 1;
return 0;
}
if (is_cross(x1, x2, x3, x4, y1, y2, y3, y4) && is_cross(x3, x4, x1, x2, y3, y4, y1, y2))
return 1;
return 0;
}
int main() {
cout << solve();
}