[Python] 10255번 교차점

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

10255번: 교차점

---

 

22/09/22

 

 

선분 교차 알고리즘을 조금 응용한 문제로, 약간의 아이디어가 있어야하는 문제이다.

---

 

문제 접근 방식:

 

 

무작정 선분 교차 알고리즘을 4번 적용하여 문제를 풀어버리면 조금 난감하다.

 

왜냐하면, 모서리에만 선이 닿는다고 했을 때, 실제로는 선분과 직사각형이 한 점에서만 만나지만, 선분 교차 알고리즘이 만나는 모서리를 포함하는 두 직선에 대해서 모두 실행되기 때문에 두 점에서 만나는 것으로 오해 될 수 있기 때문이다.

 

때문에, 선분 교차 알고리즘을 약간 변형해야한다.

 

일반적으론, 만나면 1을 반환하고 만나지 않으면 0을 반환함으로써 만남과 만나지 않음을 구분지을 수 있는데, 이런식으로 구현하면 위의 문제와 같이 중복 적용될 수 있다.

 

때문에 이 문제를 해결하기 위한 하나의 아이디어를 떠올렸는데, 이것이 이 문제의 핵심이라고 볼 수 있다.

 

바로 일반적인 경우에서 만나면 1을 반환하는데, 어떠한 선분이 다른 선분의 끝점에서 만날 때에는 1을 반환하는게 아니라 0.5를 반환하도록 하는 것이다.

 

직사각형을 이루고 있는 각 변의 양 끝점은 직사각형의 꼭짓점과 같기 때문에, 그 점과 만난다면 위에서 언급한것 처럼 무조건 2번 만날 수 밖에 없기 때문이다.

 

때문에 0.5를 반환하도록 함으로써, 두 번 만나는 걸로 해주어도 실질적으로 1을 반환하도록 하는 것과 같게끔 만들어주는 것이다.

 

그리고 교점이 무한히 많은 경우를 따로 예외처리를 해주면 된다. (다시 말해 선분이 직사각형의 한 변에 겹치면서 만나는 경우)

---

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

# 10225번 교차점
# 기하학, 선분 교차 판정, 많은 조건 분기
'''
걍 구현
'''
import sys
input = lambda: sys.stdin.readline().rstrip()

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을 반환하는 함수, 끝점에서 만나면 0.5반환
    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
            elif same_line_point_compare(p2, p3) == 0:
                return 0.5
            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 0.5
            else:
                if same_line_point_compare(p2, p4) == p4 or same_line_point_compare(p1, p4) == p1:
                    return 0
                else:
                    return 0.5
        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

T = int(input())
for _ in range(T):
    ans = 0
    xmin, ymin, xmax, ymax = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())
    x1, y1, x2, y2 = *min((x1, y1), (x2, y2)), *max((x1, y1), (x2, y2))
    if x1 == x2 or y1 == y2:
        if x1 == x2 == xmin or x1 == x2 == xmax:
            if ymin > y2 or ymax < y1:
                ans = 0
            elif ymin == y2 or ymax == y1:
                ans = 1
            else:
                ans = 4
        elif y1 == y2 == ymin or y1 == y2 == ymax:
            if xmin > x2 or xmax < x1:
                ans = 0
            elif xmin == x2 or xmax == x1:
                ans = 1
            else:
                ans = 4
        else:
            p1, p2 = (x1, y1), (x2, y2)
            p3, p4 = (xmin, ymin), (xmin, ymax)
            ans += line_seg_cross(p1, p2, p3, p4)
            p3, p4 = (xmin, ymin), (xmax, ymin)
            ans += line_seg_cross(p1, p2, p3, p4)
            p3, p4 = (xmin, ymax), (xmax, ymax)
            ans += line_seg_cross(p1, p2, p3, p4)
            p3, p4 = (xmax, ymin), (xmax, ymax)
            ans += line_seg_cross(p1, p2, p3, p4)
    else:
        p1, p2 = (x1, y1), (x2, y2)
        p3, p4 = (xmin, ymin), (xmin, ymax)
        ans += line_seg_cross(p1, p2, p3, p4)
        p3, p4 = (xmin, ymin), (xmax, ymin)
        ans += line_seg_cross(p1, p2, p3, p4)
        p3, p4 = (xmin, ymax), (xmax, ymax)
        ans += line_seg_cross(p1, p2, p3, p4)
        p3, p4 = (xmax, ymin), (xmax, ymax)
        ans += line_seg_cross(p1, p2, p3, p4)
    print(int(ans))