난이도

Platinum 5

인증

문제

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을 출력한다.

두 선분이 한 점에서 교차하는 경우 둘째 줄에 교차하는 점의 x좌표와 y좌표를 공백으로 구분해 출력한다. 한 점에서 교차하지 않는 경우에는 둘째 줄을 출력하지 않는다.

좌표의 절대/상대 오차는 10-9까지 허용한다.

예제 입력

1 1 5 5
1 5 5 1

예제 출력

1
3 3

해설 및 후기

1,2 에서 선분 교차에 대한 판정을 ccw를 이용해서 할 수 있었다. 이번에는 선분 교차점까지 구하는 것이 목표이다. 총 8개의 점을 알고 있을때, 선분의 교차점을 수식으로 쉽게 구할 수 있다. 여러 케이스의 처리가 중요한데, 특히 평행한 떨어진 선분을 처리하는 방법이나, 평행하지 않은 한 포인트로부터 연결된 선분을 찾아내고 교차점을 구하는 것이 어려웠다.

제출 코드

import sys
x1,y1,x2,y2 = map(int, sys.stdin.readline().rstrip().split())
x3,y3,x4,y4 = map(int, sys.stdin.readline().rstrip().split())

def ccw(a,b,c):
    s = (b[0]-a[0])*(c[1]-a[1]) - (b[1]-a[1])*(c[0]-a[0])

    if(s > 0): return 1
    elif (s == 0): return 0
    else: return -1

a = [x1, y1]
b = [x2, y2]
c = [x3, y3]
d = [x4, y4]
ab = (ccw(a,b,c) * ccw(a,b,d))
cd = (ccw(c,d,a) * ccw(c,d,b))

if((x1-x2)*(y3-y4)-(y1-y2)*(x3-x4) == 0):
    if(ab == 0 and cd == 0):
        min1 = min(a,b)
        max1 = max(a,b)
        min2 = min(c,d)
        max2 = max(c,d)

        if(min1 <= max2 and max1 >= min2):
            print(1)
            l = []
            if(min2 == max1):
                l.append(max1)
            if(max2 == min1):
                l.append(min1)
            if(len(l)==1):
                print(l[0][0], l[0][1])
        else:
            print(0)
    else:
        print(0)


elif(ab <= 0 and cd <= 0):
    print(1)
    try:
        px = ((x1*y2-y1*x2)*(x3-x4)-(x1-x2)*(x3*y4-y3*x4))/((x1-x2)*(y3-y4)-(y1-y2)*(x3-x4))
        py = ((x1*y2-y1*x2)*(y3-y4)-(y1-y2)*(x3*y4-y3*x4))/((x1-x2)*(y3-y4)-(y1-y2)*(x3-x4))
        print(px,py)
    except:
        pass

else:
    print(0)