BOJ - 6439 - 교차

Updated:

import sys

def isCCW(x1, y1, x2, y2, x3, y3):
    ret = (x1 * y2 + x2 * y3 + x3 * y1) - (y1 * x2 + y2 * x3 + y3 * x1)
    if ret < 0: return -1
    elif ret > 0:  return 1
    else: return 0

def isCross(x1, y1, x2, y2, x3, y3, x4, y4):
    if (
        isCCW(x1, y1, x2, y2, x3, y3) * isCCW(x1, y1, x2, y2, x4, y4) <= 0 and
        isCCW(x3, y3, x4, y4, x1, y1) * isCCW(x3, y3, x4, y4, x2, y2) <= 0):
        if (x1 < x3 and x1 < x4 and x2 < x3 and x2 < x4) or \
                (x3 < x1 and x3 < x2 and x4 < x1 and x4 < x2): return False

        if (y1 < y3 and y1 < y4 and y2 < y3 and y2 < y4) or \
                (y3 < y1 and y3 < y2 and y4 < y1 and y4 < y2): return False
        return True
    return False

def solution():
    T = int(sys.stdin.readline())
    for _ in range(T):
        xs, ys, xe, ye, xl, yt, xr, yb = map(int, sys.stdin.readline().split())

        r1 = [min(xl, xr), min(yt, yb)]
        r2 = [min(xl, xr), max(yt, yb)]
        r3 = [max(xl, xr), min(yt, yb)]
        r4 = [max(xl, xr), max(yt, yb)]

        if isCross(xs, ys, xe, ye, r1[0], r1[1], r2[0], r2[1]) or \
                isCross(xs, ys, xe, ye, r2[0], r2[1], r4[0], r4[1]) or \
                isCross(xs, ys, xe, ye, r4[0], r4[1], r3[0], r3[1]) or \
                isCross(xs, ys, xe, ye, r3[0], r3[1], r1[0], r1[1]): print("T")
        else:
            if (r1[0] < xs and r1[0] < xe and xs < r3[0] and xe < r3[0]) and \
                    (r1[1] < ys and r1[1] < ys and ys < r4[1] and ye < r4[1]): print("T")
            else: print("F")

solution()

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

Categories:

Updated:

Leave a comment