17387번: 선분 교차 2 
문제 링크: 17387번: 선분 교차 2
개요
두 선분의 양 끝 점이 주어지면 교차 여부를 출력하는 문제이다. ccw 알고리즘을 이용해 두 점이 만드는 선분에 대해 다른 한 점이 어느 방향에 위치하고 있는지를 알아낼 수 있고, 이를 이용해 교차 여부를 확인할 것이다.
풀이
ccw 함수
1
2
3
4
5
6
int ccw(int ax, int ay, int bx, int by, int cx, int cy) {
ll ans = ((ll)bx - ax) * ((ll)cy - ay) - ((ll)cx - ax) * ((ll)by - ay);
if (ans > 0) return 1;
if (ans < 0) return -1;
return 0;
}
ccw 알고리즘에 대해 [알고리즘] CCW로 세 점의 방향성 판별하기 에 잘 나와있다. ccw 함수는 점 a, b, c의 x좌표와 y좌표를 입력받아, 점 a에서 점 b방향으로 향하는 직선에 대해 점 c가 왼쪽에 있으면 1, 오른쪽에 있으면 -1, 직선상에 있으면 0을 반환한다.
main 함수
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
int main() {
pair<int, int> a, b, c, d;
scanf("%d %d %d %d", &a.first, &a.second, &b.first, &b.second);
scanf("%d %d %d %d", &c.first, &c.second, &d.first, &d.second);
int ccw1 = ccw(a.first, a.second, b.first, b.second, c.first, c.second);
int ccw2 = ccw(a.first, a.second, b.first, b.second, d.first, d.second);
int ccw3 = ccw(c.first, c.second, d.first, d.second, a.first, a.second);
int ccw4 = ccw(c.first, c.second, d.first, d.second, b.first, b.second);
//printf("%d %d %d %d\n", ccw1, ccw2, ccw3, ccw4);
//1. 어느 세 점도 일직선상에 놓여있지 않고 두 선분이 교차하는 경우
if (ccw1 * ccw2 < 0 && ccw3 * ccw4 < 0) {
printf("1");
}
//2. 두 선분이 한 직선 위에 놓인 경우
else if (ccw1 == 0 && ccw2 == 0) {
if (a > b) swap(a, b);
if (c > d) swap(c, d);
//2-1. 두 선분이 겹치는 경우 (2-1)
if (a <= d && c <= b) printf("1");
//2-2. 두 선분이 겹치지 않는 경우 (2-2)
else printf("0");
}
//3. 한 선분의 끝 점이 다른 선분이나 끝 점 위에 있는 경우 (3)
else if (ccw1 * ccw2 == 0 && ccw3 * ccw4 <= 0
|| ccw1 * ccw2 <= 0 && ccw3 * ccw4 == 0) {
printf("1");
}
else printf("0");
return 0;
}
1. 어느 세 점도 일직선상에 놓여있지 않고 두 선분이 교차하는 경우
점 a와 b가 이루는 직선에 대해 점 c와 점 d가 서로 다른 방향에 놓여있고(ccw1 * ccw2 < 0), 점 c와 점 c가 이루는 직선에 대해 점 a와 점 b가 서로 다른 방향에 놓여있는(ccw3 * ccw4 < 0) 경우에는 명백하게 두 선분이 교차함을 알 수 있다.
2. 두 선분이 한 직선 위에 놓인 경우
점 a와 b가 이루는 직선상에 점 c가 놓여있는(ccw1 == 0) 동시에 점 d도 놓여있는 경우(ccw2 == 0)는 두 선분이 한 직선 위에 놓인 경우임을 알 수 있다. 이 경우에는 점의 위치관계를 이용해서 겹치는지 확인하여 출력하면 된다.
3. 한 선분의 끝 점이 다른 선분이나 끝 점 위에 있는 경우 (3)
점 a와 b가 이루는 직선상에 점 c나 점 d가 놓여있고(ccw1 * ccw2 == 0), c와 점 c가 이루는 직선에 대해 점 a와 점 b가 서로 다른 방향에 놓여있는(ccw3 * ccw4 < 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
#include <iostream>
#pragma warning(disable:4996)
#pragma warning(disable:6031)
using namespace std;
#define ll long long
int ccw(int ax, int ay, int bx, int by, int cx, int cy) {
ll ans = ((ll)bx - ax) * ((ll)cy - ay) - ((ll)cx - ax) * ((ll)by - ay);
if (ans > 0) return 1;
if (ans < 0) return -1;
return 0;
}
int main() {
pair<int, int> a, b, c, d;
scanf("%d %d %d %d", &a.first, &a.second, &b.first, &b.second);
scanf("%d %d %d %d", &c.first, &c.second, &d.first, &d.second);
int ccw1 = ccw(a.first, a.second, b.first, b.second, c.first, c.second);
int ccw2 = ccw(a.first, a.second, b.first, b.second, d.first, d.second);
int ccw3 = ccw(c.first, c.second, d.first, d.second, a.first, a.second);
int ccw4 = ccw(c.first, c.second, d.first, d.second, b.first, b.second);
//printf("%d %d %d %d\n", ccw1, ccw2, ccw3, ccw4);
//어느 세 점도 일직선상에 놓여있지 않고 두 선분이 교차하는 경우
if (ccw1 * ccw2 < 0 && ccw3 * ccw4 < 0) {
printf("1");
}
//두 선분이 한 직선 위에 놓인 경우
else if (ccw1 == 0 && ccw2 == 0) {
if (a > b) swap(a, b);
if (c > d) swap(c, d);
//두 선분이 겹치는 경우
if (a <= d && c <= b) printf("1");
//두 선분이 겹치지 않는 경우
else printf("0");
}
//한 선분의 끝 점이 다른 선분이나 끝 점 위에 있는 경우
else if (ccw1 * ccw2 == 0 && ccw3 * ccw4 <= 0
|| ccw1 * ccw2 <= 0 && ccw3 * ccw4 == 0) {
printf("1");
}
else printf("0");
return 0;
}