[백준][기하학] 이사

BAEKJOON Online Judge(BOJ) 문제입니다.

https://www.acmicpc.net/

Baekjoon Online Judge

 

문제

https://www.acmicpc.net/problem/17371

17371번: 이사

 

내가 작성한 코드

import sys, math

read = sys.stdin.readline


def read_data():
    N = int(read().rstrip())
    points = []
    for _ in range(N):
        points.append(tuple(map(int, read().rstrip().split())))

    return N, points


def distance(x, y):
    return math.sqrt(((x[0] - y[0]) ** 2) + ((x[1] - y[1]) ** 2))


def get_min_distance(points):
    mn_distance = float('inf')
    mn_point = ()
    for i in range(len(points)):
        crnt = points[i]
        crnt_distance = max([distance(crnt, other) for other in points])
        if crnt_distance < mn_distance:
            mn_distance = crnt_distance
            mn_point = crnt
    return mn_point


N, points = read_data()
print(*get_min_distance(points))

• 브루트포스
  
  • 각 점에 대해 가장 긴 거리 구하기
  • 모든 점에 대해 구한 긴 거리 중, 가장 짧은 거리 구하기
  • 해당 점을 출력

 

다른 사람이 작성한 코드

import sys

def distance(x1, y1, x2, y2):
    return (x2-x1)**2 + (y2-y1)**2
    
n = int(input())
convini = []

for _ in range(n):
    convini.append(tuple(map(int, sys.stdin.readline().split())))

_min = 9876543210
_min_idx = -1

for i in range(n):
    _max = -1
    _m_idx = -1
    for j in range(n):
        d = distance(convini[i][0], convini[i][1], convini[j][0], convini[j][1])
        if _max < d:
            _max = d
            _m_idx = i
    if _max < _min:
        _min = _max
        _min_idx = _m_idx
        
print(convini[_min_idx][0], convini[_min_idx][1])

• 문제 접근 참고
  
  • 문제 접근 방법을 아래 블로그를 보며 참고

https://chinpa.tistory.com/58

[백준] 17371 - 이사

기억해야할 것

• 문제 접근
  
  • 세 점이 만드는 가장 짧은 거리를 찾아야 함 (가장 가까운 거리 + 가장 먼 거리)
  • 두 점을 겹쳐 가장 가까운 거리를 0으로 만듦
  • 두 점의 길이가 가장 짧은 거리를 찾기
  • 즉, 세 점이 만드는 가장 짧은 거리는 직선