백준 20149번 선분 교차 3 파이썬 플레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,000,000 ≤ x1, y1, x2, y2, x3, y3, x4, y4 ≤ 1,000,000
• x1, y1, x2, y2, x3, y3, x4, y4는 정수

구현

def findFunc(x1,y1,x2,y2):
    a=findA(x1,y1,x2,y2)
    flag = False # 특이
    if a==float('inf'):
        flag = True
        #print("x=",x1)
        if y1==y2:
            return x1,y1,True
        return x1,float('inf'), True
    b= findB(x1,y1,a)
    #print(a,"x+",b,"=y")
    return a,b,False
    
def findA(x1,y1,x2,y2):
    if x1==x2:
        return float('inf')
    else:
        return (y2-y1)/(x2-x1)
def findB(x1,y1,a):
    return y1-a*x1



def findCrossPoint(x1,y1,x2,y2,x3,y3,x4,y4):
    a1,b1,flag1= findFunc(x1,y1,x2,y2)
    a2,b2,flag2= findFunc(x3,y3,x4,y4)
    if flag1 and b1==float('inf'):# x=a1
        return a1,a2*a1+b2
    elif flag1: # (a1,b1)
        return x1,x2
    if flag2 and b2==float('inf'):
        return a2,a1*a2+b1
    elif flag2:
        return x3,x4
    else:
       # print(a2,b2,a1,b1)
        if a2!=a1:
            return  (b1-b2)/(a2-a1), (b1*a2-b2*a1)/(a2-a1)
        else: # 일직선
          #  print("어쩌지")
            if min(x1,x2)<=max(x3,x4) and min(x3,x4)<=max(x1,x2) and min(y1,y2)<=max(y3,y4) and min(y3,y4)<=max(y1,y2):
                if min(x1,x2)==max(x3,x4):
                        return min(x1,x2),min(x1,x2)*a1+b1
                if max(x1,x2)==min(x3,x4):
                        return max(x1,x2),max(x1,x2)*a1+b1
                else:
                    return float('inf'),float('inf')





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







xans=float('inf')
yans=float('inf')

answer=0
didanswer=False
def ccw(x1,y1,x2,y2,x3,y3):
    tmp= (x2-x1)*(y3-y1)- (x3-x1)*(y2-y1)
    if tmp> 0:
        return 1
    elif tmp < 0:
        return -1
    else:
        return 0
if ccw(x1,y1,x2,y2,x3,y3) * ccw(x1,y1,x2,y2,x4,y4)==0 and    ccw(x3,y3,x4,y4,x1,y1) * ccw(x3,y3,x4,y4,x2,y2)==0:
    didanswer=True
    if min(x1,x2)<=max(x3,x4) and min(x3,x4)<=max(x1,x2) and min(y1,y2)<=max(y3,y4) and min(y3,y4)<=max(y1,y2):
        answer=1
        xans, yans=findCrossPoint(x1,y1,x2,y2,x3,y3,x4,y4)

if ccw(x1,y1,x2,y2,x3,y3) * ccw(x1,y1,x2,y2,x4,y4)<=0 and    ccw(x3,y3,x4,y4,x1,y1) * ccw(x3,y3,x4,y4,x2,y2)<=0:
    if not didanswer:
        xans, yans=findCrossPoint(x1,y1,x2,y2,x3,y3,x4,y4)
        answer=1
print(answer)
if xans!=float('inf') and yans!=float('inf'):
    if xans%1==0:
        xans=round(xans)
    if yans%1==0:
        yans=round(yans)        
    print(xans,yans)
xans=float('inf')
yans=float('inf')