글 읽기 - 파이썬 반례 부탁드립니다 ㅠㅠ

hwpark12 2년 전 0

예제 입력이랑 질문글들에 있는 반례들은 다 맞는데 틀립니다 ㅠㅠ

반례나 고칠 점 부탁드릴게요...

CCW 알고리즘으로 선분 교차 판정을 했어요

def ccw(dx1, dy1, dx2, dy2):
    return dx1*dy2 - dy1*dx2
def cross(x1, y1, x2, y2, x3, y3, x4, y4):
    case = 0
    if ccw(x1-x3, y1-y3, x2-x3, y2-y3) == 0 and ccw(x1-x4, y1-y4, x2-x4, y2-y4) == 0:
        if x1 == x2 == x3 == x4:
            if y1 > y2:
                y1, y2 = y2, y1
            if y3 > y4:
                y3, y4 = y4, y3
            if y1 <= y3 <= y2 or y1 <= y4 <= y2 or y3 <= y1 <= y4 or y3 <= y2 <= y4:
                case = 3
        else:
            if x1 > x2:
                x1, x2 = x2, x1
            if x3 > x4:
                x3, x4 = x4, x3
            if x1 <= x3 <= x2 or x1 <= x4 <= x2 or x3 <= x1 <= x4 or x3 <= x2 <= x4:
                case = 2
    else:
        if ccw(x1-x3, y1-y3, x2-x3, y2-y3)*ccw(x1-x4, y1-y4, x2-x4, y2-y4) <= 0:
            if ccw(x3-x1, y3-y1, x4-x1, y4-y1)*ccw(x3-x2, y3-y2, x4-x2, y4-y2) <= 0:
                case = 1
    if case == 2:
        if x1 == x4 and y1 == y4:
            return [x1, y1]
        if x2 == x3 and y2 == y3:
            return [x2, y3]
        if not (x2 < x3 or x4 < x1):
            return 4
    if case == 3:
        if x1 == x4 and y1 == y4:
            return [x1, y1]
        if x2 == x3 and y2 == y3:
            return [x2, y3]
        if not (y2 < y3 or y4 < y1):
            return 4        
    if case == 1:
        if x1 == x2:
            x = x1
        elif x3 == x4:
            x = x3
        else:
            s1 = (y2-y1)/(x2-x1)
            s2 = (y4-y3)/(x4-x3)
            x = (s2*x3-s1*x1+y1-y3)/(s2-s1)
        if y1 == y2:
            y = y1
        elif y3 == y4:
            y = y3
        else:
            s1 = (x2-x1)/(y2-y1)
            s2 = (x4-x3)/(y4-y3)
            y = (s2*y3-s1*y1+x1-x3)/(s2-s1)
        return [x, y]
    return 0

n = int(input())
for _ in range (n):
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    x0, y0, xf, yf, x1, y1, x2, y2 = min(a[0], a[2]), min(a[1], a[3]), max(a[0], a[2]), max(a[1], a[3]), b[0], b[1], b[2], b[3]
    r1 = cross(x0, y0, xf, y0, x1, y1, x2, y2)
    r2 = cross(xf, y0, xf, yf, x1, y1, x2, y2)
    r3 = cross(xf, yf, x0, yf, x1, y1, x2, y2)
    r4 = cross(x0, yf, x0, y0, x1, y1, x2, y2)
    if r1 == 4 or r2 == 4 or r3 == 4 or r4 == 4:
        print(4)
    else:
        summ = 0
        if r1 != 0:
            summ += 1
        if r2 != 0:
            summ += 1
        if r3 != 0:
            summ += 1
        if r4 != 0:
            summ += 1
        if r1 == [x0, y0] or r1 == [xf, y0]:
            summ -= 1
        if r3 == [xf, yf] or r3 == [x0, yf]:
            summ -= 1
        print(summ)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

파이썬 반례 부탁드립니다 ㅠㅠ

hwpark12 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말