문제
2차원 좌표 평면 위의 두 선분 L1, L2가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자. 한 선분의 끝 점이 다른 선분이나 끝 점 위에 있는 것도 교차하는 것이다.
입력
첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다.
출력
L1과 L2가 교차하면 1, 아니면 0을 출력한다.
두 선분의 다양한 경우의 수를 ccw값의 부호(외적 결과의 부호)를 기준으로 정리해 보았다.
(AB X BC)*(AB X BD) 와 (CD X DA)*(CD x DB)의 부호로 보았을 때
+ + 이거나 0 + 이거나 - + 이면 무조건 안 만남
0 - 이거나 - - 이면 무조건 만남
0 0 이면은 외적 결과의 부호 만으로 알 수 없음!
따라서 0 0인 경우에만 벡터 내적의 부호를 기준으로 분류해 보았다.
(ac.ad)*(bc.bd)와 (ca.cb)*(da.db)를 기준으로 경우를 나누어 보면,
+ + 인 경우와 아닌 경우로 나눌 수 있는데,
+ + 인 경우에서 + + + +이면 만나지 않지만, + + - - 인 경우는 만나게 된다.
+ + 가 아닌 경우에는 만나게 된다.
# 선분 교차 2
def ccw(x1, y1, x2, y2, x3, y3):
cross = (x1*y2+x2*y3+x3*y1)-(x2*y1+x3*y2+x1*y3)
if cross == 0: return 0
elif cross > 0: return 1
else: return -1
import sys
result = -1
x1, y1, x2, y2 = map(int,sys.stdin.readline().split())
x3, y3, x4, y4 = map(int,sys.stdin.readline().split())
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)
if abc*abd+cda*cdb < 0: result = 1
elif abc*abd==0 and cda*cdb==0:
ac = ((x3-x1),(y3-y1)); ad = ((x4-x1),(y4-y1))
bc = ((x3-x2),(y3-y2)); bd = ((x4-x2),(y4-y2))
acad = ac[0]*ad[0]+ac[1]*ad[1]; bcbd = bc[0]*bd[0]+bc[1]*bd[1]
cacb = ac[0]*bc[0]+ac[1]*bc[1]; dadb = ad[0]*bd[0]+ad[1]*bd[1]
if acad * bcbd > 0 and cacb * dadb > 0:
result = 0 if bcbd * cacb > 0 else 1
else: result = 1
else: result = 0
print(result)