[백준 BOJ] 27718 선분 교차 EX (python)

문제 링크 : https://www.acmicpc.net/problem/27718

27718번: 선분 교차 EX

선분 교차 업그레이드 문제입니다.

주어진 모든 선분의 교차관계를 구하여야 합니다.

기존의 선분 교차 판정을 반복문을 통해 진행하므로 미리 기준 선분이 y축과 평행한지를 구해주었습니다.

또한 한 점에서 교차할 때 그 점이 어떠한 한 선분의 끝점인지 아닌지 역시 판정해 줄 필요가 있습니다.

이전의 문제들과 달리 CCW 없이 풀기에는 한계가 있어 바로 CCW를 사용해 풀이하였습니다.

길이 3773의 장문의 코드가 되어버렸지만 제출 코드중 860짜리 python 숏코딩도 CCW를 사용한 코드이니 같이 보시면 좋을 것 같습니다.

import sys

def ccw(p1_x, p1_y, p2_x, p2_y, p3_x, p3_y):
    ccw = (p2_x-p1_x)*(p3_y-p1_y)-(p3_x-p1_x)*(p2_y-p1_y)
    if ccw:
        return ccw//abs(ccw)
    return ccw

N = int(sys.stdin.readline().rstrip())
answer = [[3] * N for _ in range(N)]
lines = []
for i in range(N):
    xs1, ys1, xs2, ys2 = map(int, sys.stdin.readline().rstrip().split())
    yss = min(ys1, ys2)
    yse = max(ys1, ys2)
    xss = min(xs1, xs2)
    xse = max(xs1, xs2)
    if xss == xse:
        s_vertical = True
    else:
        s_vertical = False
    for j, (xe1, ye1, xe2, ye2) in enumerate(lines):
        xes = min(xe1, xe2)
        xee = max(xe1, xe2)
        yes = min(ye1, ye2)
        yee = max(ye1, ye2)
        if xes == xee:
            e_vertical = True
        else:
            e_vertical = False

        ccw_s1 = ccw(xs1, ys1, xs2, ys2, xe1, ye1)
        ccw_s2 = ccw(xs1, ys1, xs2, ys2, xe2, ye2)
        ccw_e1 = ccw(xe1, ye1, xe2, ye2, xs1, ys1)
        ccw_e2 = ccw(xe1, ye1, xe2, ye2, xs2, ys2)

        if ccw_s1 * ccw_s2 == 1 or ccw_e1 * ccw_e2 == 1:
            answer[i][j] = 0
            answer[j][i] = 0
        elif ccw_s1 == 0 and ccw_s2 == 0:
            if s_vertical:
                if yss == yee or yse == yes:
                    answer[i][j] = 1
                    answer[j][i] = 1
                elif yss > yee or yse < yes:
                    answer[i][j] = 0
                    answer[j][i] = 0
            else:
                if xss == xee or xse == xes:
                    answer[i][j] = 1
                    answer[j][i] = 1
                elif xss > xee or xse < xes:
                    answer[i][j] = 0
                    answer[j][i] = 0
        elif ccw_s1 == 0:
            if s_vertical:
                if yss <= ye1 <= yse:
                    answer[i][j] = 1
                    answer[j][i] = 1
                else:
                    answer[i][j] = 0
                    answer[j][i] = 0
            else:
                if xss <= xe1 <= xse:
                    answer[i][j] = 1
                    answer[j][i] = 1
                else:
                    answer[i][j] = 0
                    answer[j][i] = 0
        elif ccw_s2 == 0:
            if s_vertical:
                if yss <= ye2 <= yse:
                    answer[i][j] = 1
                    answer[j][i] = 1
                else:
                    answer[i][j] = 0
                    answer[j][i] = 0
            else:
                if xss <= xe2 <= xse:
                    answer[i][j] = 1
                    answer[j][i] = 1
                else:
                    answer[i][j] = 0
                    answer[j][i] = 0
        elif ccw_e1 == 0:
            if e_vertical:
                if yes <= ys1 <= yee:
                    answer[i][j] = 1
                    answer[j][i] = 1
                else:
                    answer[i][j] = 0
                    answer[j][i] = 0
            else:
                if xes <= xs1 <= xee:
                    answer[i][j] = 1
                    answer[j][i] = 1
                else:
                    answer[i][j] = 0
                    answer[j][i] = 0
        elif ccw_e2 == 0:
            if e_vertical:
                if yes <= ye2 <= yee:
                    answer[i][j] = 1
                    answer[j][i] = 1
                else:
                    answer[i][j] = 0
                    answer[j][i] = 0
            else:
                if xes <= xs2 <= xee:
                    answer[i][j] = 1
                    answer[j][i] = 1
                else:
                    answer[i][j] = 0
                    answer[j][i] = 0
        else:
            answer[i][j] = 2
            answer[j][i] = 2
    lines.append((xs1, ys1, xs2, ys2))
for a in answer:
    print(*a, sep='')