[python] 백준 20149 선분 교차 3

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

 

 

 

문제 해결

선분이 겹치는지 안겹치는지 확인할 때는 CCW (Counter Clock Wise)를 사용한다.

선분 1, 선분 2가 있으면 선분 1과 선분 2의 끝점 각각을 CCW를 사용했을 때 부호가 반대로 나오고 선분1의 두 끝점과 선분2를 CCW를 사용했을 때 부호가 반대로 나오면 무조건 두 선분은 만나게 된다.

문제는 끝점이 교차할 때 CCW가 0이 나올 경우가 있는데 조건을 나누어 코드를 짜야한다.

선분 1의 끝점 두개와 선분 2의 끝점을 보고 선분 1에서 x축 값이 큰 값 (x 같으면 y값)이 선분 1의 x축 값이 작은 값(x같으면 y값)보다 크고 선분 2의 작은값보다 크고 큰값보다 작으면 겹친다. (코드 참고...)

 

CODE

import sys
input = sys.stdin.readline



def check(x1, y1, x2, y2, x3, y3, x4, y4):
    if ccw(x1,y1, x3,y3, x4, y4) * ccw(x2, y2, x3, y3, x4, y4) == 0:
        if ccw(x3,y3,x1,y1,x2,y2) * ccw(x4,y4,x1,y1,x2,y2) == 0:
            if (x1,y1) > (x2, y2):
                x1, x2 = x2, x1; y1, y2 = y2, y1
            if (x3, y3) > (x4, y4):
                x3, x4 = x4, x3; y3, y4 = y4, y3
            if (x2, y2) >= (x3, y3) and (x1, y1) <= (x4, y4):
                return True
            else:
                return False
    
    if ccw(x1,y1, x3,y3, x4, y4) * ccw(x2, y2, x3, y3, x4, y4) <= 0:
        if ccw(x3,y3,x1,y1,x2,y2) * ccw(x4,y4,x1,y1,x2,y2) <= 0:
            return True
    return False

def ccw(a1, b1, a2, b2, a3, b3):
    result = (a1*b2 + a2*b3 + a3*b1) - (a1*b3 + a3*b2 + a2*b1)
    return result

if __name__ == "__main__":
    x1, y1, x2, y2 = map(int, input().split())
    x3, y3, x4, y4 = map(int, input().split())

    if check(x1, y1, x2, y2, x3, y3, x4, y4):
        print(1)
        try:
            x = ((x1*y2-y1*x2)*(x3-x4) - (x3*y4-x4*y3)*(x1-x2))/((x1-x2)*(y3-y4) - (y1-y2)*(x3-x4))
            y = ((x1*y2 - y1*x2)*(y3-y4) - (x3*y4-y3*x4)*(y1-y2))/((x1-x2)*(y3-y4)-(y1-y2)*(x3-x4))
            print(x,y)
        except:
            if (x1, y1) > (x2, y2):
                x1, x2 = x2, x1; y1, y2 = y2, y1
            if (x3, y3) > (x4, y4):
                x3, x4 = x4, x3; y3, y4 = y4, y3
            if x2 == x3 and y2 == y3:
                print(x2, y2)
            elif x1 == x4 and y1 == y4:
                print(x1, y1)

    else:
        print(0)