글 읽기 - 런타임 에러를 해결못하겠어요ㅠㅠ

wjhappyboy 4년 전 0

파이썬으로 작성한 코드인데 분할 정복을 사용하였고 예시에 있는 답도 제대로 나옵니다. 그런데 계속 런타임 에러가 나오는데 어떤 예시에서 나오는지, 어느 부분에서 나오는지 전혀 모르겠습니다. 어디가 잘못된 걸까요?ㅠㅠㅠ

import sys
import math


def shortest(st, ed, xy):
    if ed-st==1:
        return (xy[ed][0]-xy[st][0])*(xy[ed][0]-xy[st][0])+(xy[ed][1]-xy[st][1])*(xy[ed][1]-xy[st][1])
    elif ed-st==2:
        one=(xy[st][0]-xy[st+1][0])*(xy[st][0]-xy[st+1][0])+(xy[st][1]-xy[st+1][1])*(xy[st][1]-xy[st+1][1])
        two=(xy[st][0]-xy[st+2][0])*(xy[st][0]-xy[st+2][0])+(xy[st][1]-xy[st+2][1])*(xy[st][1]-xy[st+2][1])
        three=(xy[st+1][0]-xy[st+2][0])*(xy[st+1][0]-xy[st+2][0])+(xy[st+1][1]-xy[st+2][1])*(xy[st+1][1]-xy[st+2][1])
        sm=min(one, two)
        sm=min(sm, three)
        return sm
    md=(st+ed)//2
    left=shortest(st, md, xy)
    right=shortest(md+1, ed, xy)
    sm=min(left, right)
    rsm=math.sqrt(sm)
    line=(xy[md+1][0]-xy[md][0])/2
    temp=[]
    for i in range(st, ed+1):
        tmp=[]
        if xy[i][0]>line-rsm and xy[i][0]<line+rsm:
            tmp.append(xy[i][1])
            tmp.append(xy[i][0])
            temp.append(tmp)
    temp.sort()
    middle=(temp[0][0]-temp[1][0])*(temp[0][0]-temp[1][0])+(temp[0][1]-temp[1][1])*(temp[0][1]-temp[1][1])
    for i in range(len(temp)):
        for j in range(i+1, len(temp)):
            if temp[j][0]-temp[i][0]>rsm:
                break
            if (temp[j][0]-temp[i][0])*(temp[j][0]-temp[i][0])+(temp[j][1]-temp[i][1])*(temp[j][1]-temp[i][1])<middle:
                middle=(temp[j][0]-temp[i][0])*(temp[j][0]-temp[i][0])+(temp[j][1]-temp[i][1])*(temp[j][1]-temp[i][1])
    sm=min(sm, middle)
    return sm

n=int(sys.stdin.readline())
xy=[]
for i in range(n):
    x,y=map(int, sys.stdin.readline().split())
    tmp=[]
    tmp.append(x)
    tmp.append(y)
    xy.append(tmp)
xy.sort()
realxy=[]
realxy.append(xy[0])
for i in range(1, n):
    if xy[i-1][0]==xy[i][0] and xy[i-1][1]==xy[i][1]:
        continue
    else:
        realxy.append(xy[i])
n=len(realxy)
if n==1:
    print(0)
else:
    realxy.sort()
    result=shortest(0, n-1, realxy)
    print(result)
    

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

문제

문제

출처

ICPC

런타임 에러를 해결못하겠어요ㅠㅠ

wjhappyboy 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말