[BOJ] 2261 가장 가까운 두 점

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

2261번: 가장 가까운 두 점

오...
신기하다
스위핑 공부 중
풀이 보고 공부했다.

 

포인트는
1. x 좌표 기준으로 스위핑, 그러므로 y 좌표에 대한 건 범위와 관계없이 모두 다 저장해둬야 한다. 지금은 범위에 포함되지 않아도 나중에는 포함될 수 있기 때문에.
2. set은 y 좌표 기준으로 오름차순 정렬되어 있으므로, set에 있는 점의 x 좌표가 범위 안에 있는 점인지를 확인하는 게 필요하다. 이를 위해서 set에 있는 점들을 모두 확인한다면 O(n)이 소요된다. 지금 vector에는 x 좌표 기준 오름차순으로 저장되어 있기 때문에 그걸 이용하면 set 안의 내용 중에 빠져야 하는 걸 확인할 수 있다.

갑자기 궁금했다가 이해된 부분
set에서 lower_bound, upper_bound iterator 구하고 그 범위 내의 점을 모두 확인하면서 최소 거리를 구할 때 최악은 O(n) 아닌가? 했는데 그렇지 않다.

기타 사소한 거
set의 정렬 기준 설정하려고 structure 선언하면서 operator overloading 할 때 const 잘 써야 한다.

코드에서 틀렸던 부분
1. ++index 하면서 그 점을 set에서 빼야 하는데 빠뜨려서 한 번 틀렸다.
2. 각 점을 확인하고 나서 set에 넣어야 하는데 그것도 안 했다. 이건 예제 만들어서 넣어보다가 발견했다.
뭐하냐고!

struct Point {
	int x, y;
	Point() {}
	Point(int x, int y) {
		this->x = x;
		this->y = y;
	}
};

bool x_ascending_order(Point a, Point b) {
	if (a.x != b.x) {
		return a.x < b.x;
	}
	else {
		return a.y < b.y;
	}
}

struct y_ascending_order {
	bool operator() (const Point& a, const Point& b) const {
		if (a.y != b.y) {
			return a.y < b.y;
		}
		else {
			return a.x < b.x;
		}
	}
};

int GetDistSquare(Point a, Point b) {
	return pow(a.x - b.x, 2) + pow(a.y - b.y, 2);
}

int Solution(vector<Point>& point_vector, const int& n) {
	sort(point_vector.begin(), point_vector.end(), x_ascending_order);

	set<Point, y_ascending_order> available_points;
	int min_dist_square = GetDistSquare(point_vector[0], point_vector[1]);

	available_points.insert(point_vector[0]);
	available_points.insert(point_vector[1]);
	int point_in_set_index = 0;
	for (int i = 2; i < n; ++i) {
		const Point& cur = point_vector[i];
		while (point_in_set_index < i) {
			const Point& check = point_vector[point_in_set_index];
			if (pow(check.x - cur.x, 2) > min_dist_square) {
				available_points.erase(check);
				++point_in_set_index;
			}
			else {
				break;
			}
		}

		auto low_iter = available_points.lower_bound(Point(cur.x, cur.y - sqrt(min_dist_square) - 1));
		auto high_iter = available_points.upper_bound(Point(cur.x, cur.y + sqrt(min_dist_square) + 1));

		for (auto iter = low_iter; iter != high_iter; ++iter) {
			min_dist_square = min(min_dist_square, GetDistSquare(*iter, cur));
		}
		available_points.insert(cur);
	}

	return min_dist_square;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n; cin >> n;
	vector<Point> arr(n);
	for (int i = 0; i < n; ++i) {
		cin >> arr[i].x >> arr[i].y;
	}
	cout << Solution(arr, n) << kEndl;
}