BOJ 2261 - 가장 가까운 두 점 (라인스위핑)

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

 

https://www.acmicpc.net/blog/view/25

위 링크의 백준님이 설명해주신 방법 리뷰

 

<문제설명>

좌표평면 위에 최대 n개의 좌표 x,y가 주어질 때, 가장 가까운 두 점의 거리의 제곱을 구해라

(n<=1e5, -1e4<=x,y<=1e4)

 

<풀이>

모든 점을 x값 기준으로 정렬한 후에 0번~i-1번 정점에서 가장 가까운 두 점 사이의 거리를 d라고 하자.

i번 정점에 대해 가장 가까운 정점은 다음 그림에서 파란색 사각형 안의 영역에 존재한다.

 

파란색 영역에 포함되는 정점들을 set에 넣어 유지하되 y값 기준으로 탐색할 수 있도록 비교함수를 직접 짜서 넣어주면 된다.

 

<코드>

ll n, ans;
P p[MAX];

struct cmp {
	bool operator()(P p1, P p2) const {
		if (p1.second == p2.second) return p1.first < p2.first;
		return p1.second < p2.second;
	}
};

ll dist(P p1, P p2){
	return (p1.first - p2.first) * (p1.first - p2.first)
		+ (p1.second - p2.second) * (p1.second - p2.second);
}

int main() {
	FAST; cin >> n;
	for (int i = 0; i < n; i++) cin >> p[i].first >> p[i].second;
	sort(p, p + n);

	ll st = 0, ans = 2e18;
	set<P, cmp> cand;
	cand.insert(p[0]);

	for (ll i = 1,x,y; i < n; i++) {
		tie(x, y) = p[i];
		while (true) {
			if ((p[st].first - x) * (p[st].first - x) > ans) {
				cand.erase(p[st]);
				st++;
			}
			else break;
		}

		ll d = sqrt(ans) + 1;
		auto l = cand.lower_bound({ -10000, y - d });
		auto r = cand.upper_bound({ 10000,y + d });
		for (auto it = l; it != r; it++) 
			ans = min(ans, dist(*it, p[i]));
		
		cand.insert(p[i]);
	}
	cout << ans << '\n';
}

 

<생각>

사각형에 포함되는 정점수의 최대가 n이므로 O(n*n*logn)이 아닌가 의문을 제기할 수 있겠지만, d값이 단조감소함에 따라서 매 단계마다 사각형에 포함되는 정점수의 총 합을 생각해봤을 때 O(n)에 가까우므로 O(n*logn)이 되는 것 같다.