[백준/BOJ] 백준 17522번 : Canal

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

17522번: Canal

 

이분 탐색을 통해 모든 좌표끼리 거리가 x좌표 또는 y좌표를 기준으로 특점 범위 이내로 만들 수 있는지 확인하는 방법을 통해 좌표끼리 거리가 x좌표 또는 y좌표를 기준으로 최소가 되는 범위를 구하여  문제를 해결했다.

이때 좌표끼리 거리가 x좌표 또는 y좌표를 기준으로 특정 범위 이내로 만들 수 있는지 확인하는 방법은 투 포인터를 통해 구했는데, 투 포인터로 표현하는 범위(left ~ right)는 x좌표 기준으로 특정 범위를 만족하도록 하고, 투포인터로 표현하는 범위 외의 범위([0 ~ left-1] 범위 + [right+1 ~ n-1] 범위)는 y좌표 기준으로 특정 범위 이내로 만들 수 있는지 확인하는 방법을 통해 문제를 해결했다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
#include <cmath>
using namespace std;

int n;
vector<pair<int, int>> point;
vector<int> front_y_max(300005); //[해당 지점] = 0 ~ 해당 지점에서 y값의 최댓값
vector<int> front_y_min(300005); //[해당 지점] = 0 ~ 해당 지점에서 y값의 최솟값
vector<int> back_y_max(300005); //[해당 지점] = 해당 지점 ~ n-1 에서 y값의 최댓값
vector<int> back_y_min(300005); //[해당 지점] = 해당 지점 ~ n-1 에서 y값의 최솟값

//모든 좌표끼리 거리가 x좌표 또는 y좌표를 기준으로 mid 이내로 만들 수 있는지 확인
bool Check(int mid) {

	int left = 0;
	int right = 0;

	while (1) {

		// left ~ right 의 지점은 x좌표로 이미 mid이내로 만들 수 있고
		// [0 ~ left-1] 지점 + [right+1 ~ n-1] 지점(left ~ right 밖의 지점)의 좌표들을 y좌표로 mid 이내로 만들 수 있는지 확인한다

		int y_max_value = 0;
		int y_min_value = 0;

		if (left - 1 < 0 && right + 1 > n - 1) { //이미 left~right지점으로 모든 좌표들이 x좌표 기준으로 mid 이내로 만들 수 있을때
			return true;
		}

		else if (left - 1 < 0) {
			y_max_value = back_y_max[right + 1];
			y_min_value = back_y_min[right + 1];
		}

		else if (right + 1 > n - 1) {
			y_max_value = front_y_max[left - 1];
			y_min_value = front_y_min[left - 1];
		}

		else {
			y_max_value = max(back_y_max[right + 1], front_y_max[left - 1]);
			y_min_value = min(back_y_min[right + 1], front_y_min[left - 1]);
		}

		//[0 ~ left-1] 지점 + [right+1 ~ n-1]지점의 좌표들을 y좌표로 mid 이내로 만들 수 있을때
		if (y_max_value - y_min_value <= mid) {
			return true;
		}

		//더 확인할 수 없을때
		if (right + 1 >= n) {
			break;
		}

		//right+1을 포함해도 left와 거리가 x좌표 기준으로 mid 이내일때
		if (point[right + 1].first - point[left].first <= mid) {
			right++;
		}

		//right+1을 포함하면 left와 거리가 x좌표 기준으로 mid 이내가 되지 않을때
		else {
			left++;

			//left이 더 커졌을때
			if (left > right) {
				right = left;
			}
		}

	}

	return false;
}

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

	cin >> n;

	for (int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;

		point.push_back(make_pair(x, y));
	}

	//x좌표 기준으로 정렬
	sort(point.begin(), point.end());

	int here_front_y_min = numeric_limits<int>::max();
	int here_front_y_max = numeric_limits<int>::min();
	for (int i = 0; i < n; i++) {
		here_front_y_min = min(here_front_y_min, point[i].second);
		here_front_y_max = max(here_front_y_max, point[i].second);
		front_y_min[i] = here_front_y_min;
		front_y_max[i] = here_front_y_max;
	}

	int here_back_y_min = numeric_limits<int>::max();
	int here_back_y_max = numeric_limits<int>::min();
	for (int i = n - 1; i >= 0; i--) {
		here_back_y_min = min(here_back_y_min, point[i].second);
		here_back_y_max = max(here_back_y_max, point[i].second);
		back_y_min[i] = here_back_y_min;
		back_y_max[i] = here_back_y_max;
	}

	long long left = 0;
	long long right = 2000000000;
	int result = -1;
	while (left <= right) {
		long long mid = (left + right) / 2;

		if (Check(mid)) {
			result = mid;
			right = mid - 1;
		}

		else {
			left = mid + 1;
		}
	}

	cout << fixed;
	cout.precision(1);
	cout << (double)result / 2.0;

	return 0;
}