[Python] 20149번 선분 교차 3 (추후 보강 예정)

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

20149번: 선분 교차 3

---

 

22/09/22

 

 

선분 교차 2 문제를 풀었다면 거기에 교점을 구하는 코드를 추가로 집어넣음으로써 문제를 풀 수 있다.

---

 

문제 접근 방식:

 

 

이 문제를 풀기 전에 선분 교차 2 문제를 풀기를 권장한다.

 

먼저 CCW알고리즘과 이를 응용한 선분 교차 알고리즘을 이해하고 있다는 가정 하에서 서술하겠다.

 

선분 교차 알고리즘에 관한 글을 추후에 작성한다면 여기에 글을 덧붙일 예정이다.

 

어떤 선분이 교차하는지 교차하지 않는지 판단을 했다면, 그 교점을 구해야 한다.

 

그러면 두 가지 경우가 존재하는데, 교점이 무수히 많거나, 교점이 하나만 존재하거나이다.

 

근데, 교점이 무수히 많은 경우는 두 선분이 평행하면서 한 점에서 안 겹쳐야 한다.

 

두 선분이 평행하면서 한 점에서 겹치는 경우는 교점이 하나만 존재하는 경우를 고려하면 된다.

 

이를 종합하자면 다음과 같은 논리를 구성할 수 있다.

if 선분이 교차한다면?
    두 선분이 평행한지 판단
    if 두 선분이 평행하다면?
        양 끝점에서만 만나는지 판단
        if 양 끝점에서만 만난다면?
            그 교점 출력
        else
            pass
    else
        두 선분의 교점은 곧 두 직선의 교점과 같으므로, 두 직선의 교점 출력

 

이때, 두 직선의 교점은 연립 일차 방정식으로, 행렬을 이용하면 쉽게 식을 정리할 수 있다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 20149번 선분 교차 3
# 기하학, 선분 교차 판정
'''
접근 방법:
CCW알고리즘을 이용한 선분 교차판정을 진행한다.
이때 세 점이 일직선 위에 있는 경우를 고려하여 더 짜보자.
'''
def dir_vec(p1, p2): # 점 p1과 p2를 지나는 벡터를 반환하는 함수
    return (p2[0]-p1[0], p2[1]-p1[1])
def cross_product(vec_a, vec_b): # a×b을 반환하는 함수
    return vec_a[0]*vec_b[1] - vec_a[1]*vec_b[0]
def CCW(p1, p2, p3): # p1, p2, p3가 CCW를 이루고 있으면 1, CW면 -1, 일직선이면 0을 반환하는 함수
    vec_a = dir_vec(p1, p2)
    vec_b = dir_vec(p2, p3)
    k = cross_product(vec_a, vec_b)
    if k > 0:
        return 1
    elif k < 0:
        return -1
    else:
        return 0
def same_line_point_compare(p1, p2): # 같은 직선위에 있는 점을 크기 비교하여 큰 점을 반환하는 함수
    if p1[0] > p2[0]:
        return p1
    elif p1[0] < p2[0]:
        return p2
    else:
        if p1[1] > p2[1]:
            return p1
        elif p1[1] < p2[1]:
            return p2
        else:
            return 0
def point_swap(p1, p2): # 점 순서 올바르게 하는 함수
    if same_line_point_compare(p1, p2) == p1:
        return p2, p1
    else:
        return p1, p2
def line_num_swap(p1, p2, p3, p4): # 네 점이 같은 직선 위에 있을때 선분 순서를 크기대로 바꾸는 함수
    p1, p2 = point_swap(p1, p2)
    p3, p4 = point_swap(p3, p4)
    if same_line_point_compare(p1, p3) == p3:
        return p1, p2, p3, p4
    elif same_line_point_compare(p1, p3) == p1:
        return p3, p4, p1, p2
    else:
        return p1, p2, p3, p4
            
def line_seg_cross(p1, p2, p3, p4): # 선분 p1p2와 선분 p3p4가 교차하면 1 아니면 0을 반환하는 함수
    if CCW(p1, p2, p3)*CCW(p1, p2, p4) < 0 and CCW(p3, p4, p1)*CCW(p3, p4, p2) < 0:
        return 1
    else:
        if CCW(p1, p2, p3) == 0 and CCW(p1, p2, p4) == 0: # 네 점 모두 일직선에 있을때
            p1, p2, p3, p4 = line_num_swap(p1, p2, p3, p4)
            if same_line_point_compare(p2, p3) == p3:
                return 0
            else:
                return 1
        elif CCW(p1, p2, p3)*CCW(p1, p2, p4) == 0: # 세 점이 일직선에 있을때
            p1, p2 = point_swap(p1, p2)
            if CCW(p1, p2, p3) == 0:
                if same_line_point_compare(p2, p3) == p3 or same_line_point_compare(p1, p3) == p1:
                    return 0
                else:
                    return 1
            else:
                if same_line_point_compare(p2, p4) == p4 or same_line_point_compare(p1, p4) == p1:
                    return 0
                else:
                    return 1
        elif CCW(p3, p4, p1)*CCW(p3, p4, p2) == 0: # 세 점이 일직선에 있을때
            p3, p4 = point_swap(p3, p4)
            if CCW(p3, p4, p1) == 0:
                if same_line_point_compare(p4, p1) == p1 or same_line_point_compare(p3, p1) == p3:
                    return 0
                else:
                    return 1
            else:
                if same_line_point_compare(p4, p2) == p2 or same_line_point_compare(p3, p2) == p3:
                    return 0
                else:
                    return 1
        else: # 그외의 경우
            return 0

x1, y1, x2, y2 = map(int, input().split())
x3, y3, x4, y4 = map(int, input().split())
p1, p2, p3, p4 = (x1, y1), (x2, y2), (x3, y3), (x4, y4)
print(line_seg_cross(p1, p2, p3, p4))
if line_seg_cross(p1, p2, p3, p4):
    dx1 = x2 - x1
    dy1 = y2 - y1
    dx2 = x4 - x3
    dy2 = y4 - y3
    p = (dy1*x1 - y1*dx1)
    q = (dy2*x3 - y3*dx2)
    k = (-dy1*dx2 + dx1*dy2)
    if k != 0:
        x = (-dx2*p + dx1*q)/k
        y = (-dy2*p + dy1*q)/k
        print(x, y)
    else:
        p1, p2 = point_swap(p1, p2)
        p3, p4 = point_swap(p3, p4)
        if p2 == p3:
            print(*p2)
        elif p1 == p4:
            print(*p4)
        else:
            pass