[백준 5620번] 가장 가까운 두 점의 거리

문제 링크

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

5620번: 가장 가까운 두 점의 거리

---

C++ 풀이

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;

struct Point {
	int x;
	int y;
};

vector <Point>  points;
long long closest_dist;

// 두 점 사이 간의 거리 제곱값
long long dist(Point a, Point b) {
	return (((long long)b.x - a.x) * ((long long)b.x - a.x)) + (((long long)b.y - a.y) * ((long long)b.y - a.y));
}

// x좌표 오름차순 정렬
bool x_cmp(Point a, Point b) {
	if (a.x < b.x)
		return true;

	return false;
}

// Line Sweeping 방식으로 풀이
// 현재 점(idx) 기준으로 x거리 차이가 지금까지 구한 최소 거리보다 작은 점들의 거리만 구함
void find_closest(int idx) {
	double sqrt_dist = sqrt(closest_dist);
	long long d;

	// 현재 점보다 왼쪽에 위치한 점들
	for (int i = idx - 1; i >= 0; --i) {
		if ((double)points[idx].x - points[i].x < sqrt_dist) {
			d = dist(points[idx], points[i]);

			// 최소 거리 갱신
			if (d < closest_dist)
				closest_dist = d;
		}
		else
			break;
	}

	// 현재 점보다 오른쪽에 위치한 점들
	for (int i = idx + 1; i < points.size(); ++i) {
		if ((double)points[i].x - points[idx].x < sqrt_dist) {
			d = dist(points[idx], points[i]);

			// 최소 거리 갱신
			if (d < closest_dist)
				closest_dist = d;
		}
		else
			break;
	}
}

int main() {
	int N;
	cin >> N;
	points.resize(N);
	for (int n = 0; n < N; ++n)
		cin >> points[n].x >> points[n].y;
	sort(points.begin(), points.end(), x_cmp); //x좌표 기준 오름차순으로 정렬
    
	// 초기 최소 거리 값을 가장 x값이 작은 두 점 간의 거리로 설정
	closest_dist = dist(points[0], points[1]);
    
	for (int i = 0; i < N; ++i)
		find_closest(i);
	cout << closest_dist << endl;	
	return 0;
}

Line Sweeping 알고리즘을 활용하여 풀었다.

x축 기준으로 오름차순 정렬을 한 뒤, 앞에서부터 차례대로 아래 과정을 반복했다.

 

i - 1 번째 까지의 가장 가까운 두 점 간의 거리를 closest_dist라 할 때,

i 번째 점을 기준으로 왼쪽 점들, 오른쪽 점들 중 x좌표 차이가 closest_dist보다 작은 점들에 대해서만 거리를 구한다.

만약 구한 거리가 closest_dist보다 작을 경우, closest_dist를 구한 거리 값으로 갱신한다.