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

문제

평면상에 n개의 점 (P1, .... ,  Pn) 이 놓여져있다고 했을 때, 거리가 최소인 두 개의 점을 구하고 그 거리를 알고 싶다.

문제풀이

사용한 알고리즘 :  sweep line

(0) 들어가기 전에

 이 문제는 백준 2261번 문제와 거의 같습니다.
 백준님의 글 ( https://www.acmicpc.net/blog/view/25 ) 을 읽고 코드를 작성하였습니다.

(1) 코드 6~17

 각 정점을 받을 struct 를 짜주었습니다. set에 넣기 위해 operator을 함께 짜줍니다.

(2) 코드 33~34, 18~20

 각 정점을 x 좌표가 작은 것부터 오름차순으로 정렬합니다.

(3) 코드 35

 각 정점을 정렬된 차례로 탐색하며, 매 탐색시 구하고자 하는 답(이하 ans)을 최신화 합니다.
 i번째 정점 탐색을 진행할 때, 이전에 최신화한 ans보다 i번째 정점에서 멀리 떨어진 정점은 볼 필요가 없습니다.
따라서 i번째 정점 기준으로 x좌표 기준 ans 거리만큼, y좌표 기준 위,아래 각각 ans거리만큼 사각형을 만들어 이 안의 정점들만을 탐색할 것입니다. 
 이를 위해 가능성 있는 정점을 set으로 저장합니다.
 ( set 안에 저장된 정점들은 y좌표 기준으로 정렬됩니다. )
 중복을 피하기 위해 i번째 정점을 탐색시 i번째 정점 이전의 정점들과의 거리만 볼 것입니다.
(1번째와 5번째 정점 사이의 거리와 5번째와 1번째 정점 사이의 거리는 같습니다.)

(4) 코드 35~67

 우선 정렬된 정점들 중 처음 2개를 ans로 놓고, 과정(3) 에 만든 set에 그 두 정점을 넣습니다. (탐색이 끝난 정점은 set에 넣어줍니다.)
 이후 3번째 정점부터 탐색을 시작합니다.
 과정 (3)에서 말했듯이 i번째 정점을 탐색할 시 정점들을 추려서 탐색할 것입니다. 
 이를 위해
 1. i번째 정점 기준 x축으로 ans 거리 보다 멀리 있는 것은 set에서 지웁니다. ( 정점은 x좌표 기준으로 정렬되어 있기 때문에 i번째 정점 이후 정점들도 지워진 정점을 볼 필요 없습니다. )
 2. i번째 정점 기준 y축으로 위,아래로 ans 거리 안쪽에 있는 정점들만 탐색합니다.
 ( 이를 위해 정점 struct의 operator로 set을 y좌표 기준으로 만들어 준 것입니다. )
 이때 lowerbound, upperbound 를 사용해줍니다.

	#include <bits/stdc++.h>
	using namespace std;
	typedef pair<int, int> pii;
	int N;
	struct Point {
	int x, y;
	// 생성자
	Point() {}
	// 간단입력
	Point(int x1, int y1) : x(x1), y(y1) {}
	// set 에 넣기 위해 대소비교
	bool operator < (const Point& v) const { // y좌표 기준 정렬
	if (y == v.y) return x < v.x;
	else return y < v.y;
	}
	};
	bool cmp(const Point& u, const Point& v) {
	return u.x < v.x;
	}
	int dist(Point p1, Point p2) {
	return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
	}
	int main() {ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N;
	// 벡터의 배열 크기 지정
	vector<Point> P(N);
	for (int i = 0; i < N; ++i)
	cin >> P[i].x >> P[i].y;
	// x 좌표 기준 오름차순 정렬
	sort(P.begin(), P.end(), cmp);
	set<Point> candidate = { P[0],P[1] };
	int ans = dist(P[0], P[1]);
	int start = 0;
	for (int i = 2; i < N; ++i) {
	Point now = P[i];
	// x 좌표로 봐야하는 범위 자르기
	// candidate 에 저장된 값들 중 now 와의 x 좌표 차이가 ans 보다 큰 경우 제거
	while (start < i) {
	auto ST = P[start];
	int Xdist = now.x - ST.x;
	if (Xdist * Xdist > ans) {
	candidate.erase(ST);
	start++;
	}
	else break;
	}
	// y 좌표로 봐야하는 범위 = 현재 y 좌표 +- D
	int D = (int)sqrt((double)ans) + 1; // ans 는 제곱으로 저장되어 있다.
	// x좌표를 나올 수 있는 가장 작은값 -100000 으로 초기 설정
	auto lower_pt = Point(-100000, now.y - D);
	auto upper_pt = Point(100000, now.y + D);
	// struct 를 잘 짜놔서 set 에 lower_bound 바로 때려버리기
	// candidate 에 있는 point 중 lower ~ upper 사이에 있는것만 볼 것이다.
	auto lower = candidate.lower_bound(lower_pt);
	auto upper = candidate.upper_bound(upper_pt);
	// 봐야하는 y 좌표중 제일 작은 값으로 ans 최신화
	for (auto it = lower; it != upper; it++) {
	int distance = dist(now, *it);
	ans = min(ans, distance);
	}
	candidate.insert(now);
	}
	cout << ans << '\n';
	return 0;
	}

view raw BOJ 5620.cpp hosted with ❤ by GitHub