백준 2881번, 산책길 풀이

문제

백준 2881번

풀이

나무가 존재하는 좌표를 XY좌표 나누어 관리하면 이분 탐색을 사용하여 log 복잡도로 빠르게 구할 수 있습니다.

꼭짓점에 걸쳐서 겹치는 좌표는 map을 사용하면 빠르게 빼줄 수 있습니다.

소스코드

#include <bits/stdc++.h>

using namespace std;

unordered_map<int, vector<int>> xAxis, yAxis;
unordered_map<int, unordered_map<int, int>> mp;

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

	int p; cin >> p;
	while (p--) {
		int x, y; cin >> x >> y;
		xAxis[x].push_back(y);
		yAxis[y].push_back(x);

		mp[x][y] = 1;
	}

	for (auto &v : xAxis) sort(v.second.begin(), v.second.end());
	for (auto &v : yAxis) sort(v.second.begin(), v.second.end());

	int q; cin >> q;
	while (q--) {
		int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
		//(x1, y1) ~ (x1, y2), y축
		//(x1, y1) ~ (x2, y1), x축
		//(x2, y1) ~ (x2, y2), y축
		//(x2, y2) ~ (x1, y2), x축

		int ans = 0;
		ans += upper_bound(xAxis[x1].begin(), xAxis[x1].end(), y2) - lower_bound(xAxis[x1].begin(), xAxis[x1].end(), y1);
		ans += upper_bound(xAxis[x2].begin(), xAxis[x2].end(), y2) - lower_bound(xAxis[x2].begin(), xAxis[x2].end(), y1);

		ans += upper_bound(yAxis[y1].begin(), yAxis[y1].end(), x2) - lower_bound(yAxis[y1].begin(), yAxis[y1].end(), x1);
		ans += upper_bound(yAxis[y2].begin(), yAxis[y2].end(), x2) - lower_bound(yAxis[y2].begin(), yAxis[y2].end(), x1);

		if (mp[x1][y1]) ans--;
		if (mp[x1][y2]) ans--;
		if (mp[x2][y1]) ans--;
		if (mp[x2][y2]) ans--;

		cout << ans << "\n";
	}
}