[BAEKJOON] 2261번 : 가장 가까운 두 점*

문 제

 

소 스  코 드

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>

constexpr int MAX_INT{ 10'001 };

typedef std::vector<std::pair<int, int>> POINTS;
typedef std::map<std::pair<int, int>, int> VERTEX;

void PointDistance(const int&);
int Distance(POINTS&, const int&, const int&);



int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	int N;
	std::cin >> N;

	PointDistance(N);

	return 0;
}


void PointDistance(const int& N) {

	POINTS points;
	VERTEX vertexs;

	points.reserve(N);

	int x, y;
	for (int i = 0; i < N; ++i) {
		std::cin >> x >> y;
		points.emplace_back(std::make_pair(x, y));
	}

	std::sort(points.begin(), points.end());

	int dis{ Distance(points, 0, 1)};
	vertexs[std::make_pair(points[0].second, points[0].first)] = 0;
	vertexs[std::make_pair(points[1].second, points[1].first)] = 1;

	int last_index{ 0 };
	for (int i = 2; i < N; ++i) {
		while (last_index < i) {
			int x = points[i].first - points[last_index].first;
			if (x * x <= dis) break;

			vertexs.erase(std::make_pair(points[last_index].second, points[last_index].first));
			++last_index;
		}

		int dis_y{ static_cast<int>(std::sqrt(dis)) };
		auto low{ vertexs.lower_bound(std::make_pair( points[i].second - dis_y, -MAX_INT))};
		auto high{ vertexs.upper_bound(std::make_pair(points[i].second + dis_y, MAX_INT)) };

		for (auto iter = low; iter != high; ++iter) {
			dis = std::min(dis, Distance(points, (*iter).second, i));
		}
		vertexs[std::make_pair(points[i].second, points[i].first)] = i;
	}


	std::cout << dis << '\n';
}


int Distance(POINTS& p , const int& left, const int& right) {
	return ((p[right].first - p[left].first) * (p[right].first - p[left].first)) + ((p[right].second - p[left].second) * (p[right].second - p[left].second));
}

 

풀 이

 

• 라인 스위핑 -> 링크

vector를 통하여 좌료를 입력 받고, x에 대한 오름차순으로 정렬을 한다.

 

x축에 관하여 두 점간의 x거리를 구하여, 거리가 최단 거리보다 크다면, map에서 그 인덱스를 지운다.

 

이렇게 나온 x축에 관하여 최단 거리 후보를 가지고, y축에 대하여 비교를 한다. 최단거리를 통하여 lowerr_bound, upper_bound 사이에 있는 점을 가지고 최단 Min을 통하여 최솟값을 조사한다.

 

Line Sweeping에 관하여 다시 공부를 한 후 한 번 더 시도할 예정이다.

upper_bound, lower_bound를 찾을 때 pair 일 때 어떤 식으로 정해지는지 공부 할 예정이다.

 

 

출 력 값

 

 

문 제  출 처

문제 링크 : https://www.acmicpc.net/problem/2261

2261번: 가장 가까운 두 점