백준_17387_선분 교차2

문제

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

17387번: 선분 교차 2

풀이

1) CCW

세 점의 방향성을 판별할 수 있다.

2) 두 선분이 교차

3) 두 선분이 일직선

코드

import sys
input = sys.stdin.readline

x1, y1, x2, y2 = map(int, input().strip().split())
x3, y3, x4, y4 = map(int, input().strip().split())

A, B, C, D = (x1, y1), (x2, y2), (x3, y3), (x4, y4)
A, B = sorted([A, B])
C, D = sorted([C, D])

def distance(N1, N2) :
    (x1, y1), (x2, y2) = N1, N2
    return (x1-x2)**2 + (y1-y2)**2

def CCW(N1, N2, N3) : 
    (x1, y1), (x2, y2), (x3, y3) = N1, N2, N3
    return (x2-x1)*(y3-y1) - (y2-y1)*(x3-x1)

CCW_ABC = CCW(A, B, C)
CCW_ABD = CCW(A, B, D)
CCW_CDA = CCW(C, D, A)
CCW_CDB = CCW(C, D, B)

def solution() :
    # type1
    if A==C or B==D : return 1
    if A==D or B==C : return 1

    # type2
    if CCW_ABC*CCW_ABD==0 and CCW_CDA*CCW_CDB<0 : return 1
    if CCW_ABC*CCW_ABD<0 and CCW_CDA*CCW_CDB==0 : return 1

    # type3
    if CCW_ABC*CCW_ABD<0 and CCW_CDA*CCW_CDB<0 : return 1

    # type4
    if CCW_ABC==0 and CCW_ABD==0 and CCW_CDA==0 and CCW_CDB==0 : 
        if A<C and distance(A, B) > distance(A, C) : return 1
        if A>C and distance(C, D) > distance(C, A) : return 1
        
    return 0

print(solution())

참고자료

https://youngyin.tistory.com/57

백준_2166_다각형의 면적

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

17386번: 선분 교차 1