최소 외접원(점집합) 계산기

주어진 점을 모두 담는 원 중 반지름이 가장 작은 것입니다. 기지국 하나로 모든 집을 덮을 때의 최소 출력, 흩어진 사람들이 모일 때 가장 먼 사람의 이동을 줄이는 자리처럼 「최악의 경우」를 줄이는 문제가 모두 이 형태입니다.

안 됩니다. 무게중심은 거리의 제곱합을 줄이는 자리이지 가장 먼 거리를 줄이는 자리가 아닙니다. 예를 들어 점들이 한쪽에 몰려 있고 멀리 하나만 떨어져 있으면, 무게중심은 몰린 쪽으로 끌려가 필요한 반지름이 더 커집니다. 이 계산기는 두 반지름을 나란히 보여 줍니다.

언제나 두 개 또는 세 개입니다. 두 점이 원의 지름이 되거나, 세 점이 원 위에 놓입니다. 나머지 점은 원 안에 들어 있을 뿐 답을 바꾸지 않아서, 경계에 놓이지 않은 점은 조금 옮겨도 원이 변하지 않습니다.

점을 하나씩 넣어 보며 원을 키워 가는 방법입니다. 새 점이 지금 원 안에 있으면 넘어가고, 밖에 있으면 그 점이 반드시 새 원의 경계에 놓인다는 사실을 이용해 다시 풉니다. 점 순서를 섞으면 기대 시간이 점 개수에 비례하는 O(n)이 됩니다.

볼록 껍질은 점들을 감싸는 가장 작은 볼록 다각형이고, 최소 외접원은 감싸는 가장 작은 원입니다. 최소 외접원을 정하는 점들은 반드시 볼록 껍질 위에 있지만, 볼록 껍질의 꼭짓점 대부분은 원을 정하는 데 관여하지 않습니다.

됩니다. 그 경우 가장 멀리 떨어진 두 점이 지름이 되는 원이 답입니다. 세 점이 한 직선 위에 있으면 외접원이 정의되지 않으므로 이 계산기는 그런 경우를 따로 처리합니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.