글 읽기 - Python 반례가 존재할까요

khsh5592 3년 전 0

18% 쯤에서 계속 틀렸습니다가 나옵니다.

반례가 있을까요. 아니면 제가 빼먹은 조건이 있을까요.

import sys
import math

def getDegree(p1, p2):
    return p2[0] - p1[0], p2[1] - p1[1]

def ccw(p1, p2, p3):
    v, u = getDegree(p1, p2), getDegree(p2, p3)
    if v[0] * u[1] >= v[1] * u[0]: return True
    else: return False

def convex_hull(position):
    convex = []
    for p3 in position:
        while len(convex) >= 2:
            p1, p2 = convex[-2], convex[-1]
            if ccw(p1, p2, p3):
                break
            convex.pop()
        convex.append(p3)
    return convex

def getPointLength(p1, p2):
    return math.sqrt(math.pow(p2[0] - p1[0], 2) + math.pow(p2[1] - p1[1], 2))

def rotating_calipers(position):
    ret = 0
    length = len(position)-1
    j = 1
    for i in range(length):
        iNext = (i + 1) % length
        while True:
            jNext = (j + 1) % length
            vx = position[iNext][0] - position[i][0]
            vy = position[iNext][1] - position[i][1]

            ux = position[jNext][0] - position[j][0]
            uy = position[jNext][1] - position[j][1]

            temp = (0, 0)

            if ccw(temp, (vx, vy), (ux, uy)):
                j = jNext
            else:
                break
        dist = getPointLength(position[i], position[j])

        if dist >= ret:
            ret = dist
            ans1 = position[i]
            ans2 = position[j]
    return int(getPointLength(ans1, ans2) * getPointLength(ans1, ans2))

def solution():
    N = int(sys.stdin.readline())

    position = []
    for _ in range(N):
        position.append(list(map(int, sys.stdin.readline().split())))
        
    position = sorted(position, key=lambda x:(x[0], x[1]))
    ccwtemp = convex_hull(position)

    position.reverse()
    temp = convex_hull(position)

    for i in range(1, len(temp)-1):
        ccwtemp.append(temp[i])

    print(rotating_calipers(ccwtemp))

solution()

khsh5592 3년 전 0

해결했습니다. 두 점 사이의 거리를 구하는 공식 문제였내요.

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

문제

문제

출처

ICPC

Python 반례가 존재할까요

khsh5592 3년 전 0

khsh5592 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말