[PS][BOJ/6487번]-두 직선의 교차 여부

문제 설명

두 개의 직선을 나타내는 4개의 점이 입력으로 주어질 때, 두 직선이 만나는지를 확인하는 프로그램을 작성하시오.

입력

입력의 첫 번째 줄에는 테스트 케이스의 개수 N이 주어진다. (N <= 10)

다음 N개의 줄에는 각각 8개의 정수 x1, y1, x2, y2, x3, y3, x4, y4가 주어진다. 이는 두 직선 (x1, y1)-(x2, y2)와 (x3, y3)-(x4, y4)를 나타낸다.

(x1, y1)과 (x2, y2)는 서로 다른 점이며, (x3, y3)와 (x4, y4)는 서로 다른 점임이 보장된다.

모든 x와 y는 [-1000, 1000] 범위 내의 정수이다.

출력

각각의 테스트 케이스에 대해, 다음과 같이 출력한다.

두 직선이 정확히 한 점에서 만난다면, POINT x y의 꼴로 출력한다. 이는 두 직선이 (x,y)에서 교차함을 의미한다. x와 y는 정확히 소숫점 아래 둘째 자리까지 출력한다.
두 직선이 만나지 않는다면, NONE을 출력한다.
두 직선이 무한히 많은 점에서 만난다면, LINE을 출력한다.
원문에 있는 INTERSECTING LINES OUTPUT/END OF OUTPUT 등은 출력하지 않는다.

문제 분석과정

두 직선이 상태를 알기 위해선 각 직선의 지나는점(x,y)과 기울기를 알아야한다.

기울기는 Δy/Δx 이므로 각 직선의 기울기를 구해준다. 이때 주의 사항이 한가지가 있다.
기울기를 구할때 Δx가 0 이라면 ZeroDivisionError: division by zero 오류가 발생하고 기울기는 ∞ 이 된다. 따라서 if문으로 나누어서 생각할 것 이다.
기울기가 ∞이 아니라고 할때 직선간의 관계는 크게 2가지로 나눌 수 있다.

두 기울기 d1,d2 가 있을 때,

d1!=d2인 경우
d1==d2인 경우

d1==d2인 경우는 또 다시 두 가지 케이스로 나눌 수 있는데 이 두가지 케이스는 "NONE" 인지 "LINE"인지를 결정한다.

"NONE"인 경우는 같은 점을 지나지 않는 경우
"LINE"인 경우는 같은 점을 지나지 않는 경우

d1!=d2인 경우에는 생각할 것이 많지않다. 왜냐면 무조건 만나기 때문이다. (기울기 조금이라도 다르다면 반드시 어디선가 만나게 되어있다.)
따라서 해당 경우는 두 직선이 만나는 좌표를 구해주고 출력 폼에 맞게 출력해주면 된다.

이제 두 직선이 만나는 좌표룰 구해야하는데 두 직선이 만나는 좌표를 구하는 것 역시 어렵지 않다.

x,y ,d 가 있을 때,
직선은 아래와 같이 표현 할 수 있다.
$$
y = d(x-X)+Y
$$
"위 표현의 의미는 기울기가 d이고 x와 y를 지나는 직선"

이라는 것을 의미한다.

위와 같은 분석 과정 거친후 작성한 소스 코드는 다음과 같다.

소스코드

import sys 
input = sys.stdin.readline

# X,Y 는 궁금한 녀석
# 저직선위에 있니? 물어보는 함수
def isSamePoint(d,x,y,X,Y):
    if Y == d*(X-x) +y:
        return True
    else:
        return False

def findPoint(d1,d2,x1,y1,x3,y3):
    X = (y3-y1+x1*d1-x3*d2)/(d1-d2)
    Y = d1*(X-x1)+y1
    return (X,Y)

def findPointInf(d,X,x,y):
    Y = d*(X-x)+y
    return (X,Y)
# 테케 갯수 
n = int(input())

for _ in range(n):
    x1,y1,x2,y2,x3,y3,x4,y4 = map(int, input().split())

    # 기울기 무한이 아닐때 
    if x1 != x2 and x3 != x4:
        # 기울기 계산 
        d1 = (y1-y2)/(x1-x2)
        d2 = (y3-y4)/(x3-x4)
        if d1 == d2:
        # 기울기가 같고,같은점을 지난다면 => LINE
            if isSamePoint(d1,x1,y1,x3,y3):
                print("LINE")

        # 기울기가 같고,같은점을 지나지 않는다면 => NONE
            else:
                print("NONE")

        else:
        # 그외 모든경우 POINT
            point = findPoint(d1,d2,x1,y1,x3,y3)
            print("POINT {:.2f} {:.2f}".format(point[0],point[1]))

    else:
        # 둘다 무한 일때
        if x1 == x2 and x3 == x4:
            if x1==x3:
                print("LINE")
            else:
                print("NONE")

        # 둘중 하나만 무한일 때
        else:
            if  x1 == x2 :
                # d1 은 무한
                d2 = (y3-y4)/(x3-x4)

                point = findPointInf(d2,x1,x3,y3)
                print("POINT {:.2f} {:.2f}".format(point[0],point[1]))
            elif  x3 == x4 :
                d1 = (y1-y2)/(x1-x2)
                # d2 은 무한

                point = findPointInf(d1,x3,x1,y1)
                print("POINT {:.2f} {:.2f}".format(point[0],point[1]))

문제 원본
소스코드 원본

오류나 질문에 대한 문의 댓글로 남겨주겨주세요!