| [ QuizWit ] in KIDS 글 쓴 이(By): cdpark (박종대) 날 짜 (Date): 2000년 6월 9일 금요일 오후 04시 19분 46초 제 목(Title): Re: 점들사이의 거리 흑.. O(n^2)보다 빠른 게 없다는 데 한 표를 거신 분은 많지만 100원 이상 거신 분은 아무도 없군요. (부수입이 생길 찬스가...) 가장 간단히는 Delaunary Triangulation을 이용하면 O(n lg n + K) 시간에 구할 수 있습니다. (이때 K는 조건을 만족하는 쌍의 수. 최악의 경우엔 물론 O(n^2)) Delaunary Triangulation은 Voronoi Diagram의 Dual Graph입니다. 자세한 건 책을 찾아보시길... Delaunary Triangulation의 재미있는 성질은 이 중의 어떤 점에서 임의의 반지름 r인 원을 그렸을 때에 그 안에 들어오는 점들로 이루어지는 subgraph가 모두 연결되어 있다는 겁니다. (증명은 간단합니다.) 간단히 DFS나 BFS를 쓰면 찾을 수 있겠죠. Range Query 쪽을 이용해도 아마 비슷한 복잡도로 구할 수 있을겁니다. 모든 쌍을 구하는 게 아니라 그런 쌍의 갯수가 중요하다면 이 쪽을 쓰는 게 더 효율적이겠죠. -- 박.. |