취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 17423번 문제인 민원이 넘쳐흘러이다.
문제는 아래 링크를 확인하자.

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

각 스피커의 볼륨 \(V\)가 어떤 상수로 정해져있을 때 민원이 들어올지 판단하는 방법이 있을까? 민원이 들어오는 볼륨상태에서 볼륨을 높이면 민원이 들어오고 민원이 들어오지 않는 볼륨에서 볼륨을 낮추면 민원이 들어오지 않는 점을 관찰하면, 위 판단이 가능하면 이 문제를 이진 탐색(또는 parametric search)을 통해 해결할 수 있음을 알 수 있다.

그러면 볼륨이 정해져 있을 때 민원이 들어올지 여부를 어떻게 판단해야 할지 생각해보자. 만약 각 스피커로부터 음악이 들리는 범위가 축과 평행한 사각형 모양이었다면 segment tree와 line sweep 테크닉을 이용해 이를 해결할 수 있을 것이다. 그러나 이 문제에서는 음악이 들리는 범위가 축과 45도를 이루는 사각형 모양을 하고 있다.

그렇다면 좌표평면의 축을 45도 돌려서 생각하면 어떨까? 축을 45도 돌려서 생각하면 스피커로부터 음악이 들리는 범위를 축과 평행한 사각형 모양으로 다룰 수 있게 된다. 또한 단순히 축을 돌리기만 하지 않고 적절한 상수배까지 적용하면 모든 좌표를 정수가 되게끔 할 수 있다. 여기까지 생각해낸다면 남은 문제를 해결하는 방법은 잘 알려져있고, 이를 구현해 문제를 쉽게 해결할 수 있다.

축을 회전해 각 점에 새로운 좌표를 부여할 때, 신경쓰지 않으면 새로운 좌표로 음수가 부여되어 문제가 생길 수 있다는 점에 유의하자.

아래는 제출한 소스코드이다.

//45도 회전 + sweepline seg + binary search
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

int N;
int seg[8388609][2];
int upd(int L, int R, int qL, int qR, int qVal, int sI) {
	if (seg[sI][1]) {
		seg[sI][0] += seg[sI][1] * (R - L + 1);
		if (L < R) seg[sI * 2][1] += seg[sI][1], seg[sI * 2 + 1][1] += seg[sI][1];
		seg[sI][1] = 0;
	}
	if (R < qL || qR < L) return seg[sI][0];
	if (qL <= L && R <= qR) {
		seg[sI][0] += qVal * (R - L + 1);
		if (L < R) seg[sI * 2][1] += qVal, seg[sI * 2 + 1][1] += qVal;
		return seg[sI][0];
	}
	return seg[sI][0] = upd(L, (L + R) / 2, qL, qR, qVal, sI * 2) + upd((L + R) / 2 + 1, R, qL, qR, qVal, sI * 2 + 1);
}

int qry(int L, int R, int qL, int qR, int sI) {
	if (seg[sI][1]) {
		seg[sI][0] += seg[sI][1] * (R - L + 1);
		if (L < R) seg[sI * 2][1] += seg[sI][1], seg[sI * 2 + 1][1] += seg[sI][1];
		seg[sI][1] = 0;
	}
	if (R < qL || qR < L) return 0;
	if (qL <= L && R <= qR) return seg[sI][0];
	return qry(L, (L + R) / 2, qL, qR, sI * 2) + qry((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1);
}

int spow[100000]; int P[100000][2];
vector<pair<pair<int, int>, pair<int, int>>> qvec;

int ansL = 0, ansR = 999999;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++) cin >> spow[i];
	for (int i = 0; i < N; i++) cin >> P[i][0] >> P[i][1];

	while (ansL < ansR) {
		memset(seg, 0, sizeof(seg));
		qvec.clear();
		int mid = (ansL + ansR) / 2 + 1;
		for (int i = 0; i < N; i++) {
			int p = spow[i] * mid;
			int &x = P[i][0], &y = P[i][1];
			qvec.emplace_back(make_pair(make_pair(x - y - p, 1), make_pair(x + y - p + 1000000, x + y + p + 999999)));
			qvec.emplace_back(make_pair(make_pair(x - y + p, -1), make_pair(x + y - p + 1000000, x + y + p + 999999)));
		}
		sort(qvec.begin(), qvec.end());

		bool chk = 1;
		for (auto &q:qvec) {
			int L = q.second.first, R = q.second.second;
			if (q.first.second < 0) upd(1, 3000000, L, R, -1, 1);
			else {
				if (qry(1, 3000000, L, R, 1)) {
					chk = 0;
					break;
				}
				upd(1, 3000000, L, R, 1, 1);
			}
		}

		if (chk) ansL = mid;
		else ansR = mid - 1;
	}

	cout << ansL;
}