(BOJ6439 교차

• tags : (algorithm

  No matching post could be found

• 문제 링크 : https://www.acmicpc.net/problem/6439
• 풀이 링크
  • Python

• 선분 교차 판별 문제인데, 사각형 내부에 있는지도 판별해야한다.
  • 선분 교차는 총 4번을 진행하면 되고
  • 사각형 내부에 있는지 확인할 때, 문제에서 지나가듯이 언급한 ‘변수명은 우연의 일치’ 부분을생각하며 풀어야 한다.

x1, y1, x2, y2, x3, y3, x4, y4 = map(int, input().split())
A, B = (x1, y1), (x2, y2)
if A > B:
    A, B = B, A
X, Y, Z, W = (x3, y3), (x3, y4), (x4, y4), (x4, y3)
if check_inside(A, B, Y, W):
    print("T")
    continue

• 조금 다른 방식으로 풀어낼 수 있는데, 문제를 조금 착각하여 풀이가 그렇게 예쁘지는 않은 것 같다.
• 우선 선분의 왼쪽 아래, 오른쪽 위 점으로 각각 A, B로 선언했다.
• 그리고 사각형의 네 점을 구한뒤, 사각형 내부에 있는지 확인한다.

def check_inside(A: Point, B: Point, LB: Point, RT: Point) -> bool:
    xl, xr = min(LB[0], RT[0]), max(LB[0], RT[0])
    yb, yt = min(LB[1], RT[1]), max(LB[1], RT[1])
    if xl <= A[0] <= xr and yb <= A[1] <= yt:
        if xl <= B[0] <= xr and yb <= B[1] <= yt:
            return True
    return False

• 사각형 내부에 선분이 있는지 확인하는 함수
• 여기서, 변수명은 우연의 일치라는 부분을 고려해야 하는데, bottom, top과 같은 변수가 사각형의 아래, 위의 부분은 나타내지 않을 수 있다.
  • 그래서 양 끝 두점을 가져와 x, y좌표 각각을 기준으로 왼쪽과 오른쪽, 위와 아래를 min, max함수로 구하고,
  • 선분의 두 끝점이 내부에 속하는지 확인한다.

for C, D in ((Y, X), (Y, Z), (Z, W), (X, W)):
    if C > D:
        C, D = D, C
    if chceck_line(A, B, C, D):
        print("T")
        break
else:
    print("F")

• 선분 교차 판별을 위해서 for문을 순회하고
  • 만약 교차하는 경우를 발견하면 T출력 후 break,
  • 아니면 for문을 모두 순회 후 F출력

def chceck_line(A: Point, B: Point, C: Point, D: Point) -> bool:
    tmp1 = get_ccw(A, B, C) * get_ccw(A, B, D)
    tmp2 = get_ccw(C, D, A) * get_ccw(C, D, B)
    if not tmp1 and not tmp2:
        if A <= D and B >= C:
            return True
        return False
    if tmp1 <= 0 and tmp2 <= 0:
        return True
    return False

• 선분 교차 판별 함수는 다음과 같이 구했는데,
• 우선 ccw값들을 구하여 곱한 후 연산 준비를 하고,
  • 경우의 따라 분류하여 교차하는지 아닌지를 반환한다.