20149. 선분 교차 3
업데이트 시간 : 2023-04-03 05:23:19 +0000[Platinum IV] 선분 교차 3 - 20149
성능 요약
메모리: 113112 KB, 시간: 164 ms
분류
기하학, 많은 조건 분기, 선분 교차 판정
문제 설명
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까지 허용한다.
💡 Solutions
📄 선분 교차 3.py
x1,y1,x2,y2 = list(map(int,input().split()))
x3,y3,x4,y4 = list(map(int,input().split()))
p1 = (x1,y1)
p2 = (x2,y2)
p3 = (x3,y3)
p4 = (x4,y4)
# 이렇게 4개의 좌표가 있다고 하고, ab, cd 두 선분이 있다고 했을 때
# 두 선분이 교차하는지를 보려면, ab와 ac의 외적값과 ab와 ad의 외적 값을 곱해 음수가 나오고
# cd와 ca, cd와 cb의 외적값 곱이 음수가 나오면 된다.
# [출처] 2차원 벡터의 외적 특성|작성자 대꼬
def cp(a,b,c):
v1 = [b[0] - a[0], b[1] - a[1]]
v2 = [c[0] - b[0], c[1] - b[1]]
return v1[0]*v2[1] - v1[1]*v2[0]
# 직선의 방정식 구하기 https://mathbang.net/443#gsc.tab=0
# 좌표값 찾기는 니 알아서 하세요^^ 머리 깨지겠네ㅎ
def point():
a1 = (y2-y1)
b1 = (x2-x1)
c1 = (x2*y1 - x1*y2) # (x2-x1)*y1 - (y2-y1)*x1 이기 때문
a2 = (y4-y3)
b2 = (x4-x3)
c2 = (x4*y3 - x3*y4) # (x4-x3)*y3 - (y4-y3)*x3 이기 때문
x = (c2*b1 - c1*b2)/(b2*a1 - b1*a2)
y = (c2*a1 - c1*a2)/(b2*a1 - b1*a2)
return (x,y)
if (max(x1,x2) < min(x3,x4) or max(x3,x4) < min(x1,x2)) or (max(y1,y2) < min(y3,y4) or max(y3,y4) < min(y1,y2)):
print(0)
else:
# 외적의 특징을 이용해서 교점의 존재 유무를 찾음
case1 = cp(p1, p2, p3) * cp(p1, p2, p4)
case2 = cp(p3, p4, p1) * cp(p3, p4, p2)
if case1 <= 0 and case2 <= 0:
print(1)
# 기울기가 동일한 경우 한 점만 만날 수 있는 case 가 존재한다 + 겹치는 경우는 배제해줘야한다.
# 에제 6번
if (y2-y1)*(x4-x3) == (y4-y3)*(x2-x1):
if max(x1,x2) == min(x3,x4) or max(x3,x4) == min(x1,x2):
if p1 in (p3,p4): print(*p1)
elif p3 in (p1,p2): print(*p3)
else:
print(*point())
else:
print(0)