098 선분 교차 2

첫번째 코드

 

선분이 교차하는 경우를 책의 개념을 통해 이해했다.

뭔가 이해보다는 암기의 느낌이 강했다...ㅋㅋㅋㅋ

 

ABC: AB를 기준으로 C의 CCW 구하기

ABD: AB를 기준으로 D의 CCW 구하기

CDA: CD를 기준으로 A의 CCW 구하기

CDB: CD를 기준으로 B의 CCW 구하기

 

선분이 교차하는 경우

ABC * ABD = 음수 and CDA * CDB = 음수

0인 경우 min max x, y를 통해 구할 수 있다!!

 

코드는 책을 참고했다.

 

import sys
input = sys.stdin.readline

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

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

def isOverlab(x1, y1, x2, y2, x3, y3, x4, y4):
    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):
        return True
    return False

def isCross(x1, y1, x2, y2, x3, y3, x4, y4):
    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:
        return isOverlab(x1, y1, x2, y2, x3, y3, x4, y4)
    
    elif abc * abd <= 0 and cda * cdb <= 0:
        return True
    
    else:
        return False

cross = isCross(x1, y1, x2, y2, x3, y3, x4, y4)

if cross:
    print(1)
else:
    print(0)

 

통과!

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Gold/17387.%E2%80%85%EC%84%A0%EB%B6%84%E2%80%85%EA%B5%90%EC%B0%A8%E2%80%852

programmers/백준/Gold/17387. 선분 교차 2 at main · ornni/programmers