APIO 2018 Circle selection

만약 모든 원의 반지름이 같다면, 격자를 반지름*반지름의 부분 정사각형으로 나눈 뒤, 원의 중심을 중심으로 하는 25개의 부분 정사각형만 봐서 지우면 된다. 모든 원의 크기가 다를 때도 이와 비슷한 전략을 쓸 수 있다. 부분 정사각형의 크기가 현재 탐색하는 원의 반지름 이상이면서 반지름의 2배보다 작도록 하면 탐색하는 범위 밖의 정사각형이 없지도, 부분 정사각형이 너무 커져서 의미가 없어지지도, 부분 정사각형을 그리느냐고 시간을 많이 쓰지도 않게 된다. 

시간 복잡도: N*25*unordered_map으로 인한 매우 큰 상수로, 시간이 빡빡한 편이다.

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>
#define int long long
using namespace std;
unordered_map<int, vector<int>>x;
int po[300100][2];
vector<pair<int, int>>so;
int pre[300100];
int num[300100];
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int N;
	cin >> N;
	int i;
	for (i = 0; i < N; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		a += 1LL << 30;
		b += 1LL << 30;
		pre[i] = c;
		so.push_back({ -c,i });
		po[i][0] = a;
		po[i][1] = b;
	}
	sort(so.begin(), so.end());
	int gr = 30;
	for (i = 0; i < N; i++)
	{
		x[po[i][0] / (1LL << gr) * (1LL << 31) + po[i][1] / (1LL << gr)].push_back(i);
	}
	for (i = 0; i < N; i++)
	{
		if (num[so[i].second])
			continue;
		while ((1LL << gr) >= -so[i].first * 2)
		{
			gr--;
			x.clear();
			int i;
			for (i = 0; i < N; i++)
			{
				if (num[i])
					continue;
				x[po[i][0] / (1LL << gr) * (1LL << 31) + po[i][1] / (1LL << gr)].push_back(i);
			}
		}
		int cuuu = so[i].second;
		int xx = po[cuuu][0] / (1LL << gr);
		int y = po[cuuu][1] / (1LL << gr);
		int j, k;
		for (j = xx - 2; j <= xx + 2; j++)
		{
			for (k = y - 2; k <= y + 2; k++)
			{
				if (!x.count(j * (1LL << 31) + k))
					continue;
				for (auto l = x[j * (1LL << 31) + k].begin(); l != x[j * (1LL << 31) + k].end(); l++)
				{
					if (num[*l])
						continue;
					int le = *l;
					
					int xxx = (po[cuuu][0] - po[le][0]);
					int yyy = (po[cuuu][1] - po[le][1]);
					int rrr = (-so[i].first + pre[le]);
					if (xxx * xxx + yyy * yyy <= rrr * rrr)
					{
						num[le] = cuuu + 1;
					}
				}
			}
		}
	}
	for (i = 0; i < N; i++)
	{
		cout << num[i] << ' ';
	}
}