최소 피복 반경 n 치수

이것을 해결할 수있는 알려진 알고리즘이 있습니까?최소 피복 반경 n 치수

2016-11-01 Guru

물론 사용할 수있는 알고리즘이 있습니다. 어떤 종류의 시간 복잡성을 달성하려고합니까? – ollpu

이것은 알고리즘을 요청하고 코드가 깨진 경우 도움이되지 않습니다. – thecoshman

센터도 정수입니까, 아니면 반으로 될 수 있습니까? – m69

욕심 알고리즘을 풀 수있어 관련 문제있다 : 주어진 점과 반경이 원의 최소 수를 찾을 수 있습니다. 이 알고리즘은 왼쪽 가장자리가 x로 정렬 된 점에서 시간 O (n)에서 실행되는 가장 왼쪽의 숨겨진 점 위에 놓이는 원을 반복 배치합니다.

요청 된 문제에 대한 알고리즘을 얻으려면 점을 한 번 정렬 한 다음 이진 검색을 사용하여 최대 반원 수를 초래하는 최소 반경을 찾으십시오. x 좌표가 기계어로 표현 될 수 있다고 가정하면, 이것은 잘되어야합니다. (그렇지 않은 경우 다른 알고리즘이 있습니다.)

출처

2016-11-01 18:21:31

@Blender 그는 이진 검색을 사용하여 답변을 제안하고 그에 동의합니다. 이 질문과 유사 : [링크] (http://stackoverflow.com/questions/40189551/arrange-n-items-in-k-nonempty-groups-such-that-the-difference-between-the-minimu/40205972 # 40205972) 및 [링크] (http://stackoverflow.com/questions/39673898/divide-array-into-k-contiguos-partitions-such-that-sum-of-maximum-partition-is-m/39675098# 39675098) – Tempux