[Python] 백준 - 20149 선분 교차 3

 

문제해결방법 - 

 

1. 사선공식(신발끈 공식)을 이용하면 주어진 3점의 좌표 방향에 따라 1, 0, -1을 출력한다는 것을 알 수 있다.

 

1) (x1, y1) (x2, y2) 직선에서 각 점 (x3, y3) 과 (x4, y4)을 사선공식으로 돌린다. 결과를 곱했을 때, 0, -1의 경우만 교점이 있을 가능성이 있다.

2) (x3, y3), (x4, y4) 직선에서도 각 점 (x1, y1) 과 (x2, y2)을 사선공식으로 돌린다. 위와 같다.

 

2. 위 결과가 둘 다 0, -1인 경우만 본다. 예외적으로 기울기가 같을 때, 만나지 않는 경우가 있을 수 있으므로, 범위를 체크한다. <- 여기서 기울기가 같으면서 만나지 않는 경우가 추려진다.

 

1) 두 직선의 기울기가 같을 때, 접점이 하나면 p1, p2 중 공통되는 부분이 접점이 된다.

2) 두 직선의 기울기가 같을 때, 접점이 많으면 check1함수의 False로 인해 접점은 출력하지 않게 된다.

 

3. 기울기가 같지 않고, A, B가 1이 아니라 해(접점)가 있을 경우,  두 직선의 방정식을 연립하여, (x, y)좌표로 표현되는 해(접점)를 출력한다. (위 조건대로 진행할 경우, 접점이 있고 그 접점은 하나일 것이므로)

4. A, B는 -1이거나 0일 때만 접점이 있다는 말이 되므로, 그외 경우라면 0을 출력한다.

 

 

 

코드

import sys
sys.setrecursionlimit(10**6)
from collections import deque
input = sys.stdin.readline

x1, y1, x2, y2 = map(int, input().split())
x3, y3, x4, y4 = map(int, input().split())
p1, p2, p3, p4 = (x1, y1), (x2, y2), (x3, y3), (x4, y4)
ans = 0

def ccw(a, b, c):
	l = a[0]*b[1]+b[0]*c[1]+c[0]*a[1]
	r = b[0]*a[1]+c[0]*b[1]+a[0]*c[1]
	if l-r < 0:
		return 1
	elif l-r == 0:
		return 0
	else:
		return -1

def check1(a, b, c, d):
	return min(a, b) == max(c, d) or max(a, b) == min(c, d)

def check2(x1, x2, x3, x4, y1, y2, y3, y4):
	A = min(x1, x2) > max(x3, x4) or min(x3, x4) > max(x1, x2)
	B = min(y1, y2) > max(y3, y4) or min(y3, y4) > max(y1, y2)
	return A or B

def sol(p1, p2, p3, p4):
	a1 = p2[1]-p1[1]
	b1 = p1[0]-p2[0]
	c1 = p1[0]*p2[1]-p1[1]*p2[0]

	a2 = p4[1]-p3[1]
	b2 = p3[0]-p4[0]
	c2 = p3[0]*p4[1]-p3[1]*p4[0]

	x = (b2*c1-b1*c2)/(a1*b2-a2*b1)
	y = (a2*c1-a1*c2)/(a2*b1-a1*b2)
	return (x, y)

A = ccw(p1, p2, p3) * ccw(p1, p2, p4)
B = ccw(p3, p4, p1) * ccw(p3, p4, p2)

if A <= 0 and B <= 0 and not check2(x1, x2, x3, x4, y1, y2, y3, y4):
	print(1)
	if (x2-x1)*(y4-y3) == (x4-x3)*(y2-y1):
		if check1(x1, x2, x3, x4):
			if p1 in [p3, p4]:
				print(*p1)
			elif p2 in [p3, p4]:
				print(*p2)
	else:
		print(*sol(p1, p2, p3, p4))
else:
	print(0)