BOJ - 2389 - 세상의 중심에서…

Updated:

import sys
import math

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

def solution():
    N = int(sys.stdin.readline())
    standard = [0, 0]
    point = []

    for _ in range(N):
        x, y = map(float, sys.stdin.readline().split())
        standard[0] += x
        standard[1] += y
        point.append([x, y])

    standard[0] /= N
    standard[1] /= N

    step = 0.1
    ret = 0

    for i in range(30000):
        ret = 0
        number = 0
        for j in range(N):
            distance = getDistance(standard, point[j])
            if distance > ret:
                number = j
                ret = distance

        standard[0] += (point[number][0] - standard[0]) * step
        standard[1] += (point[number][1] - standard[1]) * step
        step *= 0.999

    print("%0.10f %0.10f %0.10f"
        %(standard[0], standard[1], ret)
    )

solution()

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

Categories:

Updated:

Leave a comment