[백준 20149번] 선분 교차 3 (Python3)

import sys
input = sys.stdin.readline

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

def eq1(x,y):
  return (x2-x1)*(y-y1)-(y2-y1)*(x-x1)

def eq2(x,y):
  return (x4-x3)*(y-y3)-(y4-y3)*(x-x3)

def check():
  if eq1(x3,y3)*eq1(x4,y4) <= 0 and eq2(x1,y1)*eq2(x2,y2) <= 0:
    if x2-x1 == x4-x3 == 0:
      if max(y1,y2)>min(y3,y4) and max(y3,y4)>min(y1,y2):
        return 1,0
      if max(y1,y2)==min(y3,y4): 
        return 1, (x1,max(y1,y2))
      if max(y3,y4)==min(y1,y2):
        return 1, (x1,min(y1,y2))
    elif (y4-y3)*(x2-x1) == (y2-y1)*(x4-x3):
      if y1-(y2-y1)/(x2-x1)*x1 == y3-(y4-y3)/(x4-x3)*x3:
        if max(x1,x2)>min(x3,x4) and max(x3,x4)>min(x1,x2):
          return 1,0
        if max(x1,x2)==min(x3,x4):
          if x1>x2:
            return 1,(x1,y1)
          return 1,(x2,y2)
        if max(x3,x4)==min(x1,x2):
          if x3>x4:
            return 1,(x3,y3)
          return 1,(x4,y4)
    else:
      return 1, cross()
  return 0,0

def cross():
  a1 = y2-y1
  b1 = -(x2-x1)
  a2 = y4-y3
  b2 = -(x4-x3)
  c1 = (y2-y1)*x1-(x2-x1)*y1
  c2 = (y4-y3)*x3-(x4-x3)*y3
  k = a1*b2-a2*b1
  x = b2*c1-b1*c2
  y = -a2*c1+a1*c2
  return x/k,y/k

crossed,co = check()

if crossed:
  print(1)
  if co:
    print(co[0],co[1])
else:
  print(0)

 

선분교차 2까지 푼김에 3도 있길래 풀었다. 선분교차 2와 차이점은 교점이 1개 존재할 경우, 교점의 좌표까지 구해주어야 한다는 것이다.

 

결국 연립방정식을 풀어야하는건데, 어떻게 풀까 고민하다가 대학에서 배웠던 선형대수학개론이 기억났다. 선대개 그렇게 싫어하던 과목이었는데 역시 다 배우는 이유가 있구나!

 

행렬의 역함수를 이용하면 쉽게 연립방정식을 풀 수 있다. cross 함수 참고

 

그 외에는 선분교차 2와 거의 유사하다.

 

 

오늘의 교훈) 배움에는 다 이유가 있다