[백준] 20149 선분 교차 3, python

https://www.acmicpc.net/problem/20149

 

 

 

 

 

 

두 선분의 교차 판정(1), python

두 선분의 교차 판정(1), python

 

 

두 선분의 교차 여부와, 교점이 1개일때 그 교점의 좌표를 구하는 문제이다.

 

 

매개변수 방정식을 이용해 연립방정식의 해를 구한다.

만약 해가 존재할시 구한 매개변수를 대입하여 좌표를 구할수 있다.

 

 

해가 존재하지 않을시에는 두 선분이 평행한지, 한 직선위에 있는지 체크해서 평행하다면 교점이 없는것이고, 한 직선위에 있다면 두 선분의 양 끝점의 좌표를 비교해서 교차되는지 확인한다.

 

 

두 선분이 한 직선위에 있는 경우, 두 선분의 끝에서 교점이 생기게 되면 교점이 1개이므로 예외쳐리를 해주었다.

 

 

 

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

a = x2-x1; b = -(x4-x3); e = x3-x1
c = y2-y1; d = -(y4-y3); f = y3-y1
p1 = (x1,y1);p2 = (x2,y2);p3 = (x3,y3);p4 = (x4,y4);

# 매개변수 방정식을 이용한 선분교차 체크
def solve(a,b,c,d,e,f):
    if a*d-b*c == 0:
        # 두 선분이 한 직선위에 있는 경우
        if d*e-b*f == 0:
            # 두 선분의 끝에서 교점이 생기는 경우
            if max(min(p1,p2),min(p3,p4))==min(max(p1,p2),max(p3,p4)):
                print(1)
                print(*max(min(p1,p2),min(p3,p4)))
            elif max(min(p1,p2),min(p3,p4))<min(max(p1,p2),max(p3,p4)):
                print(1)
            else:
                print(0)
        # 두 선분이 평행한 경우
        else:
            print(0)
    else:
        s = (d*e-b*f)/(a*d-b*c)
        t = (a*f-c*e)/(a*d-b*c)
        # s,t가 0이상 1이하인 경우 교점이 존재한다
        if 0<=s<=1 and 0<=t<=1:
            print(1)
            print(x1+s*(x2-x1),y1+s*(y2-y1))
        else:
            print(0)

solve(a,b,c,d,e,f)