mintchoco

(BOJ20149 선분 교차 3

Link copied to clipboard

문제 설명

Link copied to clipboard
  • 이 글은 텍스트와 코드 기반으로 작성되어, 이해가 어려울 수 있음.
  • 문제는 매우 간단하다.
    • 두 선분의 끝점이 주어지고, 교차하는지 판별하면 된다.
  • 우선, 선분 교차를 잘 이해하고 해결하기 위해 CCW과 관련한 지식이 필요하다.
    • 두 선분이 있을 때, 전혀 다른 위치이면 오히려 쉽게 판별할 수 있지만, 만약 두 선분이 일직선상에 있는 등의 경우를 판별할 때 편리하게 할 수 있다.
  • 만약 선분위치를 분류하면 크게 3가지로 분류가 된다.
    • 하나의 직선 위에 있는 경우
    • 교차할 수 있는 위치
    • 교차할 수 없는 위치
  • 그리고 각 경우를 잘 구분하여 문제를 해결한다.

문제 풀이

Link copied to clipboard
x1, y1, x2, y2 = MIIS()
x3, y3, x4, y4 = MIIS()
ccw1 = ccw(x1, y1, x2, y2, x3, y3)
ccw2 = ccw(x1, y1, x2, y2, x4, y4)
ccw3 = ccw(x3, y3, x4, y4, x1, y1)
ccw4 = ccw(x3, y3, x4, y4, x2, y2)

tmp1, tmp2 = ccw1 * ccw2, ccw3 * ccw4
  • 우선 총 주어진 4개의 점에 대한 ccw를 구하고,
    • 각각 선분 기준으로 구한 ccw끼리 곱한다.
    • 이렇게 하면, 하나의 선분 기준으로 다른 선분의 두 점의 위치를 파악할 수 있다.
if not tmp1 and not tmp2:
    if (x1, y1) > (x2, y2):
        x1, y1, x2, y2 = x2, y2, x1, y1
    if (x3, y3) > (x4, y4):
        x3, y3, x4, y4 = x4, y4, x3, y3
    if (x1, y1) <= (x4, y4) and (x2, y2) >= (x3, y3):
        print(1)
        get_point((x1, y1), (x2, y2), (x3, y3), (x4, y4))
    else:
        print(0)
  • 만약 tmp1, tmp2 값이 모두 0인경우는 두 선분이 하나의 직선 위에 있거나, 하나의 점을 공유하는 경우이다.
    • 이 때, 두 선분의 위치를 판별하기 위해 왼쪽 아래의 점, 오른쪽 위의 점으로 구분하고,
    • 선분이 교차하는 경우 1을 출력, 아니면 0을 출력한다.
    • 선분이 교차하는 경우 교점이 유일한지 확인한다. 해당 함수는 뒤에서 다시 다루겠다.
if tmp1 <= 0 and tmp2 <= 0:
    print(1)
    get_point((x1, y1), (x2, y2), (x3, y3), (x4, y4))
else:
    print(0)
  • 위의 경우가 아니라면, 선분이 교차하거나 교차하지 않는 경우다.
  • 만약 선분이 교차하려면 tmp1, tmp2의 값 모두 0이하가 되야 하고,
    • 역시 1을 출력, 교점을 확인한다.
def get_point(A: tuple, B: tuple, C: tuple, D: tuple):
    x1, y1 = A
    x2, y2 = B
    x3, y3 = C
    x4, y4 = D
    m = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4)
    if m:
        x = ((x1 * y2 - y1 * x2) * (x3 - x4) - (x1 - x2) * (x3 * y4 - y3 * x4)) / m
        y = ((x1 * y2 - y1 * x2) * (y3 - y4) - (y1 - y2) * (x3 * y4 - y3 * x4)) / m
        print(x, y)
    else:
        if B == C and A <= C:
            print(*B)
        elif A == D and C <= A:
            print(*A)
  • 교점을 찾는 함수
  • 도 선분을 직선으로 생각하여, 두 교점을 찾고 출력한다.

참조

Link copied to clipboard