[BOJ/Python] 6439_교차

문제 출처:https://www.acmicpc.net/problem/6439

6439번: 교차

문제

입력으로 주어진 선분과 직사각형이 교차하는지 아닌지를 구하는 프로그램을 작성하시오.

위의 그림에서 선분의 시작점은 (4,9), 끝점은 (11,2) 이며, 직사각형의 왼쪽 위 좌표는 (1,5), 오른쪽 아래 좌표는 (7, 1)이다. 또, 선분과 직사각형은 교차하지 않는다.

선분과 직사각형이 교차하려면 적어도 한 점을 공유해야한다. 입력으로 주어지는 좌표는 모두 절댓값이 50보다 작거나 같은 정수이지만, 교점은 정수 좌표가 아닐 수도 있다. 직사각형의 넓이는 0일 수도 있다.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, xstart ystart xend yend xleft ytop xright ybottom로 이루어져 있다. (xstart, ystart)는 선분의 시작점, (xend, yend)는 선분의 끝점이고, (xleft, ytop)는 직사각형의 한 쪽 모서리 좌표, (xright, ybottom)는 직사각형 반대쪽 모서리 좌표이다.

xleft ytop xright ybottom 은 직사각형의 왼쪽, 오른쪽, 위, 아래 좌표를 의미하는 것은 아니며, 변수명은 우연의 일치이다.

출력

각 테스트 케이스마다 선분과 직사각형이 교차하면 'T'를, 교차하지 않으면 'F'를 한 줄에 하나씩 출력한다. 선분의 두 점이 사각형 내부에 있을 때도 'T'이다.

예제 입력 1

1
4 9 11 2 1 5 7 1

예제 출력 1

F

 

---

풀이

 

CCW 알고리즘을 이용하여 풀었다.

CCW 알고리즘에 대한 설명은 아래 게시글에 작성해두었다.

CCW(counter clockwise) 알고리즘

우선 문제의 조건을 살펴보면 다음과 같다.

• 선분의 양 끝 좌표가 주어진다.
• 직사각형의 양쪽 끝 모서리(대각선 방향)의 좌표가 주어진다.
• 선분과 직사각형의 교점이 생길 경우 T, 아닐 경우 F를 출력한다.
• 선분이 직사각형 내부에 존재할 경우 T를 출력한다.

문제를 풀기 위해 다음과 같이 접근을 하였다.

• 직사각형의 양쪽 끝 모서리의 좌표를 이용하면 직사각형의 네 꼭짓점의 좌표를 구할 수 있다.
• 이를 이용하면 직사각형의 변, 즉 4개의 선분을 구할 수 있다.
• 이 4개의 선분과 주어진 선분을 CCW 알고리즘을 이용하여 교차하는지 판단을 한다.
• 추가적으로 선분이 직사각형 내부에 존재할 때는 교차하지 않는 경우이므로, 따로 처리해 준다.

코드는 다음과 같다.

 

import sys
 
def ccw(pa,pb,pc):
    if pa[0] * pb[1] - pb[0] * pa[1] > 0:
        result1 = -1
    elif pa[0] * pb[1] - pb[0] * pa[1] < 0:
        result1 = 1
    else:
        result1 = 0
    
    if pa[0] * pc[1] - pc[0] * pa[1] > 0:
        result2 = -1
    elif pa[0] * pc[1] - pc[0] * pa[1] < 0:
        result2 = 1
    else:
        result2 = 0
 
    return result1*result2
 
def check(xy1,xy2,xy3,xy4):
    if min(xy1[0],xy2[0])<=xy3[0]<=max(xy1[0],xy2[0]) and min(xy1[1],xy2[1])<=xy3[1]<=max(xy1[1],xy2[1]) or \
        min(xy1[0],xy2[0])<=xy4[0]<=max(xy1[0],xy2[0]) and min(xy1[1],xy2[1])<=xy4[1]<=max(xy1[1],xy2[1]) or \
        min(xy3[0],xy3[0])<=xy1[0]<=max(xy3[0],xy3[0]) and min(xy3[1],xy4[1])<=xy1[1]<=max(xy3[1],xy4[1]) or \
        min(xy3[0],xy3[0])<=xy2[0]<=max(xy3[0],xy3[0]) and min(xy3[1],xy4[1])<=xy2[1]<=max(xy3[1],xy4[1]):
        return True
    else:
        return False
        
 
t = int(sys.stdin.readline())
 
for _ in range(t):
    x_start,y_start,x_end,y_end,x1,y1,x2,y2 = map(int,sys.stdin.readline().split())
    xy_list = [[x1,y1],[x1,y2],[x2,y2],[x2,y1]]
 
    p = [x_end - x_start, y_end - y_start]
    
    p_list=[]
    for i in range(4):
        p_list.append([xy_list[i][0] - x_start, xy_list[i][1] - y_start])
 
 
    flag = False
    if min(x1,x2)<=min(x_start,x_end) and max(x_start,x_end)<=max(x1,x2) and \
        min(y1,y2)<=min(y_start,y_end) and max(y_start,y_end)<=max(y1,y2):
        flag = True
 
    else:
        for i in range(4):
            ans = ccw(p,p_list[i-1],p_list[i])
            if ans==-1:
                p1 = [xy_list[i][0]-xy_list[i-1][0],xy_list[i][1]-xy_list[i-1][1]]
                p2 = [x_start - xy_list[i-1][0],y_start - xy_list[i-1][1]]
                p3 = [x_end - xy_list[i-1][0],y_end - xy_list[i-1][1]]
                if ccw(p1,p2,p3)==-1:
                    flag = True
                    break
            elif ans==0:
                if check([x_start,y_start],[x_end,y_end],xy_list[i-1],xy_list[i]):
                    flag = True
                    break
 
    if flag:
        print("T")
    else:
        print("F")

 

1. 테스트의 수 t를 입력받아 t만큼 수행한다.
2. 선분의 좌표와 직사각형의 양쪽 끝 모서리의 좌표를 입력받는다.
3. 직사각형의 양쪽 끝 모서리의 좌표를 이용하여 네 꼭짓점의 좌표를 구하여 xy_list에 저장한다.
4. 선분의 벡터 p를 만든다.
5. 반복문을 이용하여 선분의 한 점과 직사각형의 네 꼭짓점 사이의 벡터를 만든다.
6. 만약 선분이 직사각형 내부에 존재한다면 flag를 True로 설정한다. (True라면 교차 판단할 이유가 없다.)
7. 만약에 내부에 존재하지 않는다면 직사각형의 네 점을 차례대로 접근하여 교차판단을 시작한다.
8. 함수 ccw는 pa와 pb의 외적을 구하고, pa와 pc의 외적을 구하여 곱한 값을 반환한다. (외적은 벡터이므로, 정확히는 z값)
9. 결괏값이 -1이라면, 선분의 한 점을 기준으로 직사각형의 두 점이 반대방향에 있으므로 교차의 가능성이 있다.
10. 직사각형의 두 점 중, 한 점을 기준으로 선분의 양 끝점과 직사각형의 나머지 한 점을 향하는 벡터를 만든다.
11. ccw를 수행하여 이번에도 -1이 나온다면, 교차한다는 뜻이므로 flag를 True로 바꾸고 반복문을 종료한다.
12. 만약 처음 ccw를 수행했을 때의 결과가 0이라면, 한 점에 접하거나, 선분과 직사각형의 한 변에 겹치는 부분이 존재할 수도 있다. (평행, 수직 한 방향으로 만나지 않을 수도 있다.)
13. 따라서 접하거나 겹치는 부분이 생기는지 확인하기 위해 check 함수를 이용하여 판단한다.
14. 최종적으로 flag가 True라면 T를 출력하고 아니라면 F를 출력한다.