문제
풀이
CCW를 이용하여 선분 교차를 확인하는 문제이다. 선분 교차 1에서는 세 점이 일직선이 되는 경우가 없는 경우이며, 선분 교차 2 문제는 세 점이 일직선이 되는 경우도 포함한 문제이다.
CCW를 이용하여 abc와 abd가 서로 반대 방향이면서, cda와 cdb가 서로 반대 방향이면 교차하는 가장 일반적인 경우이다.
세 점이 일직선이 되는 경우도 고려해주어야 되는데, 이 경우, a가 d보다는 작아야 하며, b가 c보다 큰 경우 서로 한 일직선 상에서 b-c만큼 교차하게 된다. 이 경우만을 따로 고려해주면 되는 문제이다.
소스 코드
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
import sys
from math import *
def ccw(x1, y1, x2, y2, x3, y3):
result = (x1*y2 + x2*y3 + x3*y1) - (x1*y3 + x3*y2 + x2*y1)
if(result > 0): #반시계방향
return 1
elif(result < 0): #시계방향
return -1
else: #일직선
return 0
x1, y1, x2, y2 = map(int, input().split()) #a, b
x3, y3, x4, y4 = map(int, input().split()) #c, d
abc = ccw(x1, y1, x2, y2, x3, y3)
abd = ccw(x1, y1, x2, y2, x4, y4)
cda = ccw(x3, y3, x4, y4, x1, y1)
cdb = ccw(x3, y3, x4, y4, x2, y2)
ans = 0
didans = False
if(abc*abd == 0 and cda*cdb == 0): # 두 직선이 일직선상에 있을 수 있는 경우
didans = True
if(min(x1, x2) <= max(x3, x4) and max(x1, x2) >= min(x3, x4) and min(y1, y2) <= max(y3, y4) and max(y1, y2) >= min(y3, y4)): # 두 직선이 일직선상에 있으며, A <= D && B >= C
ans = 1
if (abc*abd <= 0 and cda*cdb <= 0): # 일단 두 직선이 교차 될 가능성이 있는 경우
if not didans: # 두 직선이 일직선상에 있을 수 없는 경우
ans = 1 # 가장 일반적인 케이스이므로 ans = 1
print(ans)
