취미로 코딩하기

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

이번에 볼 문제는 백준 30630번 문제인 직각삼각형의 동생은?이다.
문제는 아래 링크를 확인하자.

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

이 문제의 쿼리들은 입력으로 미리 모두 주어지므로, 주어지는 쿼리들을 임의의 순서대로 처리한 다음 입력으로 주어진 순서대로 그 답들을 출력하여 문제를 해결할 수 있다(오프라인 쿼리).

주어진 검은색 점들과 쿼리를 나타내는 점들을 "원점과 이은 반직선"과 \(x\)축이 이루는 각의 크기를 기준으로 정렬해 차례대로 하나씩 살펴보자(각도 기준 스위핑). 이 때 여러 점이 같은 각을 가진다면 검은색 점을 먼저 살펴보자. 검은색 점은 지금까지 살펴본 점들에 추가하고, 쿼리를 나타내는 점은 보일 때마다 지금까지 살펴본 점 중 \(x\)좌표가 자신 이하인 점의 개수를 답으로 계산하면 문제를 해결할 수 있을 것이다.

글쓴이는 위 과정을 구현하는 방법으로 pbds를 사용하였다. 좌표압축과 세그먼트트리를 활용한 구현 또한 가능하나, 주관적으로는 그 구현량이 적지 않고 간단한 편도 아니므로 pbds를 이용한 구현이 더 깔끔한 것 같다.

이 문제는 언젠가 대회에 나가면 활용할 생각으로 pbds 템플릿을 암기한 이래 처음으로 본격적인 문제 풀이에 활용해본 문제라 기억에 남을 것 같다.

pbds가 무엇인지는 링크를 참고하자.

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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename K> using ordered_set = tree<K, null_type, less<K>, rb_tree_tag, tree_order_statistics_node_update>;

bool comp(pair<pair<int, int>, int> &p1, pair<pair<int, int>, int> &p2) {
	ll val1 = (ll)p1.first.second * p2.first.first, val2 = (ll)p2.first.second * p1.first.first;
	if (val1 != val2) return val1 < val2;
	return p1.second < p2.second;
}
int N, M;
vector<pair<pair<int, int>, int>> Q;
ordered_set<pair<int, int>> st;
int ans[100001];

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

	cin >> N;
	while (N--) {
		int x, y; cin >> x >> y;
		Q.emplace_back(make_pair(make_pair(x, y), 0));
	}
	cin >> M;
	for (int m = 1; m <= M; m++) {
		int x, y; cin >> x >> y;
		Q.emplace_back(make_pair(make_pair(x, y), m));
	}
	sort(Q.begin(), Q.end(), comp);
	for (auto &p:Q) {
		if (p.second) ans[p.second] = st.order_of_key(make_pair(p.first.first + 1, -1));
		else st.insert(p.first);
	}

	for (int i = 1; i <= M; i++) cout << ans[i] << '\n';
}