[백준 17387번] 파이썬 - 선분교차 2

백준 17387_선분교차2

시간제한 0.25초(추가 시간 없음) 메모리제한 512MB

# 조건

• 2차원 좌표 평면 위의 두 선분 L1, L2가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자. 한 선분의 끝 점이 다른 선분이나 끝 점 위에 있는 것도 교차하는 것이다.
• L1의 양 끝 점은 (x1, y1), (x2, y2), L2의 양 끝 점은 (x3, y3), (x4, y4)이다

입력

• 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다.

출력

• L1과 L2가 교차하면 1, 아니면 0을 출력한다.

제한

• -1,000,000 ≤ x1, y1, x2, y2, x3, y3, x4, y4 ≤ 1,000,000
• x1, y1, x2, y2, x3, y3, x4, y4는 정수
• 선분의 길이는 0보다 크다.

# 접근 방법

• ccw 알고리즘을 이용하여 풀어준다.

https://cheon2308.tistory.com/entry/Algorithm-CCW-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

• 선분 AB와 선분 CD가 교차하려면, 선분 AB를 기준으로 C와의 방향과 D와의 방향이 서로 달라야 한다.
  • 즉, CCW(A, B, C) * CCW(A, B, D)의 값이 음수여야 한다.
• 선분 CD의 입장에서 마찬가지이다.
  • CCW(C, D, A) * CCW(C, D, B)의 값이 음수여야 한다.
• 즉, CCW(A, B, C) * CCW(A, B, D) <= 0 && CCW(C, D, A) * CCW(C, D, B) <= 0 이면, 교차한다고는 일단 할 수 있다.
• 네 직선이 한 직선상에 존재하는 경우 -> ccw 의 곱이 0이다.
  • 직선이 교차일 가능성이 있지만, 선분이 만나지 못하는 경우 -> 0보다 크거나 같다.
  • 즉, 모든 조건을 확인하기 위하여 4번의 ccw를 수행해주면 된다.

17386 번의 경우 세 점이 일직선에 있는 경우가 없지만 이번 문제는 일직선에 있는 경우도 생각해주어야 한다.
- 이 경우 x 값의 범위, y 값의 범위 끼리 겹치는지 확인해주면 된다.

• 즉, c가 b보다 작고 a가 d 보다 작아야 된다.

import sys  
sys.stdin = open('input.txt')  

def ccw(x1, y1, x2, y2, x3, y3):  
    tmp = (x2-x1)*(y3-y1) - (x3-x1) *(y2-y1)  
    if tmp >0:  
        return 1  
    elif tmp < 0:  
        return -1  
    else:  
        return 0  

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

answer = 0  
flag = False  

if ccw(x1, y1, x2, y2, x3, y3) * ccw(x1, y1, x2, y2, x4, y4) == 0 and ccw(x3, y3, x4, y4, x1, y1) * ccw(x3, y3, x4, y4, x2, y2 ) == 0:  
    flag = True  
    if min(x1, x2) <= max(x3, x4) and min(x3, x4) <= max(x1, x2) and min(y1, y2) <= max(y3, y4) and min(y3, y4) <= max(y1, y2):  
        answer = 1  
if ccw(x1, y1, x2, y2, x3, y3) * ccw(x1, y1, x2, y2, x4, y4) <= 0 and ccw(x3, y3, x4, y4, x1, y1) * ccw(x3, y3, x4, y4, x2,  y2) <= 0:  
    if not flag:  
        answer = 1  
print(answer)