글 읽기 - 가장 가까운 두 점, 파이썬 라인 스위핑 시간초과... 도와주세요

anywhere133 3년 전 0

C++로 짜여진 라인 스위핑 알고리즘을 참고하여,

파이썬으로 구현하여 해결하려고 했습니다.

시간 초과가 뜨는 걸 보니, 아마도 케이스가 많은 경우에서 시간이 많이 걸리는 것 같습니다.

어느 부분을 수정해야 수행시간이 조금 더 빨라질 수 있을까요?.

혹은 제가 생각하지 못한 반례가 있을까요?

import sys, math

def dist(a, b):
    x = a[0] - b[0]
    y = a[1] - b[1]
    return x ** 2 + y ** 2

def upperbound(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        mid = (left + right) // 2
        if arr[mid] <= target:
            left = mid + 1
        else:
            right = mid
    return right

def lowerbound(arr, target):
    left, right = 0, len(arr) - 1

    while left < right:
        mid = (left + right) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    return right

n = int(sys.stdin.readline())
dots = [tuple(map(int, sys.stdin.readline().rstrip().split(' '))) for _ in range(n)]
dots.sort(key= lambda x: x[0])

y_map = [dots[0], dots[1]]
ans = dist(dots[0], dots[1])
last = 0
for i in range(2, n):
    if ans == 0:
        break
    now = dots[i]
    while last < i:
        p = dots[last]
        dx = now[0] - p[0]
        if dx * dx <= ans:
            break
        y_map.remove(p)
        last += 1

    d = math.sqrt(ans)
    y_map.sort(key=lambda x: x[1])
    low = lowerbound(list(map(lambda x : x[1], y_map)), now[1] - d)
    upper = upperbound(list(map(lambda x: x[1], y_map)), now[1] + d)
    for m in y_map[low:upper+1]:
        ans = min(ans, dist(now, m))

    y_map.append(now)

print(ans)

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

문제

문제

출처

ICPC

가장 가까운 두 점, 파이썬 라인 스위핑 시간초과... 도와주세요

anywhere133 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말