Go Go Gorelians

• 주어진 조건대로 트리를 구성한 뒤에, 트리의 중심을 구하는 문제.
• 트리를 구성하기 위해서, 점을 추가할때마다 이전에 추가된 점들중 가장 가까운 점을 찾는 것은, 점이 전부 1000개 이하이기 때문에 모든 점과의 거리를 모두 계산해보는 나이브한 방식으로도 충분히 돌아간다. 이 과정에서의 시간복잡도는 O(n^2)
• 트리의 중심을 구하는 것은 링크에 설명한 방법으로 O(n)에 처리할수 있다. (이것도 나이브한 방식으로 O(n^2)에 구현하더라도 돌아가는데에는 문제 없을듯.)
• 총 시간복잡도는 O(n^2)

"""Solution code for "BOJ 4618. Go Go Gorelians".

- Problem link: https://www.acmicpc.net/problem/4618
- Solution link: http://www.teferi.net/ps/problems/boj/4618

Tags: [tree diameter]
"""

import math
import sys

from teflib import psutils
from teflib import tree as ttree


@psutils.run_until_all_zero
def main():
    N = int(sys.stdin.readline())
    tree = [[] for _ in range(N)]
    coords, ids = [], []
    for u in range(N):
        ID, *coord = [int(x) for x in sys.stdin.readline().split()]
        coords.append(coord)
        ids.append(ID)
        if u == 0:
            continue
        p = min(range(u), key=lambda x: math.dist(coord, coords[x]))
        tree[u].append(p)
        tree[p].append(u)

    answer = sorted(ids[u] for u in ttree.DistanceMeasures(tree).centers)
    print(*answer)


if __name__ == '__main__':
    main()

• Dependency: teflib.tree.DistanceMeasures