[BOJ 17522] Canal

문제

BOJ 17522 Canal

유형

• 이분탐색
• 투 포인터

풀이

풀이가 떠오르지 않아서 여러 코드를 찾아보았다.

투 포인터가 익숙하지 않아서 풀이가 잘 떠오르지 않았던 것 같다.
x좌표간의 길이가 될 수있는 0~2e9 사이의 값을 이분탐색하면서 진행한다. 기준 값을 d라고 했을 때

시작과 끝점을 0번 인덱스로 잡고 두 좌표의 x 거리가 d 이하일 때 나머지 점들의 y 좌표간 최대 거리가 d 이하인지를 계산한다.

예를 들어 N개의 전체 좌표 중 인덱스 a~b의 x좌표 최대 거리가 d일 때 미리 저장해두었던 a-1까지의 y의 최대 최소 좌표와 b+1까지의 최대 최소 좌표를 미리 저장해두면 O(1)으로 a~b의 좌표를 제외한 좌표들의 최대 최소 y좌표를 구할 수 있고 y 거리가 d이하인지를 확인할 수 있다.

만약 x, y 거리가 모두 d 이하이면 저장해두고 더 작은 d를 찾기 위해 이분탐색을 이어 나간다.

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <fstream>

const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,-1,0,1 };

using namespace std;

int n;

pair<int, int> v[300001];
int frontYMax[300001];
int frontYMin[300001];
int backYMax[300001];
int backYMin[300001];


bool solve(int d) {
    int s = 0, e = 0;
    while (s <= e && e < n) {
        if (v[e].first - v[s].first <= d) {
            if (s == 0 && e == n - 1) return true;

            int MaxY = -1e9, MinY = 1e9;
            if (s > 0) {
                MaxY = frontYMax[s - 1];
                MinY = frontYMin[s - 1];
            }
            if (e < n - 1) {
                MaxY = max(MaxY, backYMax[e + 1]);
                MinY = min(MinY, backYMin[e + 1]);
            }

            if (MaxY - MinY <= d) return true;
			e++;
        }
        else s++;
    }
    return false;
}

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

	cin >> n;
	for (int i = 0; i < n; i++) 
        cin >> v[i].first >> v[i].second;

	sort(v, v + n);

	frontYMax[0] = frontYMin[0] = v[0].second;
	backYMax[n - 1] = backYMin[n - 1] = v[n - 1].second;
	for (int i = 1; i < n; i++) {
		frontYMax[i] = max(frontYMax[i - 1], v[i].second);
		frontYMin[i] = min(frontYMin[i - 1], v[i].second);
		backYMax[n - 1 - i] = max(backYMax[n - i], v[n - 1 - i].second);
		backYMin[n - 1 - i] = min(backYMin[n - i], v[n - 1 - i].second);
	}

	long long l = 0, r = 2e9, mid;
	long long ans;
	while (l <= r) {
		mid = (l + r) / 2;
		if (solve(mid)) {
			ans = mid; r = mid - 1;
		}
		else l = mid + 1;
	}

	cout << ans / 2 << '.' << (ans % 2 == 0 ? 0 : 5);

	return 0;
}