글 읽기 - 어디가 잘못된건가요?? 진짜 모르겠습니다 ㅠㅠ

museum114 4년 전 0

질문 글에 올라와있는 테스트 케이스를 돌리니 나와야 하는 output보다 더 적은 값이 나오는 건 무슨 경우죠...?

Divide and Conquer 로 풀려고 했습니다...

가운데 index를 기준으로 왼쪽과 오른쪽으로 구역을 나눠서 재귀한다.
왼쪽과 오른쪽 각각에서 도출된 최소거리 중 더 작은 값을 temp_distance에 저장한다.
중심 축의 x좌표로부터 temp_distance 보다 적게 떨어진 점을 penetrate 라는 list에 저장한다.
penetrate를 y좌표를 기준으로 정렬한다.
이중 for문을 통해서 각 점을 비교하는데 이 때 y축의 좌표간 거리가 알려진 최소거리보다 멀면 바로 break한다.
결과값을 return 한다

왜 안되는 걸까요?

from operator import itemgetter
from math import sqrt, ceil, floor
import sys

def input_read():
    how_many = int(input())
    coordinate_system = []

    for i in range(how_many):
        coordinate_system.append(list(map(int, input().split())))

    coordinate_system.sort(key=itemgetter(0))
    print(int(shorted_distance(coordinate_system)) ** 2)

def distance(x1, y1, x2, y2):
    return sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)


def shorted_distance(system):
    mini = sys.maxsize
    length = len(system)
    
    ######## 좌표로 주어진 점들의 총 개수가 홀수냐 짝수냐에 따라 케이스를 나눴습니다. 
    ##이 부분은 중간 선을 어디로 할 것인가, 이걸 정하는 부분입니다.
    
    if length % 2 != 0:
        dividing_line = system[int(length/2)][0]
    else:
        temp = floor(length / 2)
        dividing_line = (system[temp-1][0] + system[temp][0]) / 2     
        
            ###########################################################
            
            
    ## 좌표 개수가 2개나 3개라면 다른 스킬을 쓰지않고 무식하게 구합니다. ####
    if len(system) == 2:
        return distance(system[0][0], system[0][1], system[1][0], system[1][1])

    if len(system) == 3:
        return min(distance(system[0][0], system[0][1], system[1][0], system[1][1]),
                   distance(system[0][0], system[0][1], system[2][0], system[2][1]),
                   distance(system[1][0], system[1][1], system[2][0], system[2][1]))
    
    ## 양쪽으로 분할하는 과정입니다.

    left_side = system[:ceil((length / 2.0))]
    right_side = system[ceil((length / 2.0)):]

    ####
    
    ## 왼쪽과 오른쪽에서 나오는 최소 거리 중 누가 더 적냐를 판단합니다.
    temp_distance = min(shorted_distance(left_side), shorted_distance(right_side))

    ## penetrate 라는 list를 만들어서 중심축의 x좌표로부터 최소거리에 있는 점들만 모읍니다.
    
    penetrate = []
    for i in range(length):
        if abs(dividing_line - system[i][0]) < temp_distance:
            penetrate.append(system[i])
    penetrate.sort(key=itemgetter(1))  # y축 기준으로 정렬

    ## 그리고 y축 기준으로 정렬합니다.
    
    
    for i in range(len(penetrate)):
        for j in range(i + 1, len(penetrate)):
            if penetrate[j][1] - penetrate[i][1] >= temp_distance:
                break    ## x 좌표 끼리 거리가 최소거리보다 길면 break를 해줍니다.
            if abs(penetrate[j][0] - penetrate[i][0]) >= temp_distance:
                continue

            mini = distance(penetrate[i][0], penetrate[i][1],\
                            penetrate[j][0], penetrate[j][1])
            if temp_distance > mini:
                temp_distance = mini

    return temp_distance

input_read()

djm03178 4년 전 0

정말로 이 코드가 제출했던 코드 그대로인가요? 주석으로 설명을 덧붙이는 건 좋지만, 적어도 실행되는 코드 자체는 제출했던 코드 그대로에서 한 글자도 다르지 않게 해주세요.

입력 받는 부분을 주석처리해놓고 신경쓰지 않아도 된다고 하시면 어떻게 실행을 시켜야 할지 모르겠습니다.

museum114 4년 전 0

그 부분을 생각하지 못했네요... 죄송합니다.

코드는 수정했습니다.

kyunamk 4년 전 0

sqrt를 사용하면.. data의 유실이 발생합니다.

distance 내부 처리를 제곱으로 관리하면.. 아무래도 그러한 error는 없을 거 같은데..

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

문제

문제

출처

ICPC

어디가 잘못된건가요?? 진짜 모르겠습니다 ㅠㅠ

museum114 4년 전 0

djm03178 4년 전 0

museum114 4년 전 0

kyunamk 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말