[BOJ] 2261번: 가장 가까운 두 점

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


모든 점을 전수조사하면 $O(N^2)$이 걸립니다. 대신에 divide and conquer로, 점들을 우선 x좌표 기준으로 정렬한 뒤, y축과 평행한 적절한 기준선으로 점을 두 그룹(그룹1, 그룹2)으로 나눕니다. 그룹1 내에서의 최소인 거리를 d1, 그룹2 내에서의 최소인 거리를 d2라고 할 때 d = min(d1, d2)라고 잡고 기준선으로부터 x축 거리가 d 이하로 떨어진 점들만 수집해 y축으로 정렬하고 나면 비둘기집의 원리에 의해 각 점에서 인접한 6개의 점만 살펴보면 됩니다.


시간복잡도는 $O(N(lgN)^2)$이 됩니다.


https://github.com/encrypted-def/BOJ/blob/master/2261.cpp

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 1068번: 트리  (0) 2018.01.07
[BOJ] 1007번: Vector Matching  (0) 2018.01.07
[BOJ] 1006번: 습격자 초라기  (0) 2018.01.07
[BOJ] 2515번: 전시장  (0) 2018.01.07
[BOJ] 2306번: 유전자  (0) 2018.01.07
[BOJ] 2300번: 기지국  (0) 2018.01.07
  Comments