[python] 백준 17386 선분 교차 1

https://www.acmicpc.net/problem/17386

17386번: 선분 교차 1

 

문제 해결

• CCW를 사용하는 문제
• CCW는 외적을 이야기 한다.
• 우선 두 직선이 일직선 위에 있는 경우가 없으므로 평행하거나 일치, 여러점이 겹치는 것을 생각할 필요가 없다.
• 따라서 L2의 끝 두점 (x3,y3), (x4,y4)와 L1의 두 끝점 (x1,y1), (x2,y2)을 CCW로 계산해서 양수가 하나라도 나오면 교차를 하지 않는다.

 

CODE

import sys
input = sys.stdin.readline

def CCW(x1,y1,x2,y2,x3,y3):
    a= x1*y2 + x2*y3 + x3*y1 - (x1*y3+x3*y2+x2*y1)
    if a <0:
        return 1 #시계방향
    elif a == 0:
        return 0 # 일직선
    else:
        return -1 # 반시계방향
x1,y1,x2,y2 = map(int, input().split())
x3,y3,x4,y4 = map(int, input().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<=0 and cda*cdb<=0:
    print(1)
else:
    print(0)