#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
gp_hash_table<int, int> table;
using namespace std;
typedef long long ll;
typedef long double ld;
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(pair <int, int> x) const {
static const uint64_t FIXED_RANDOM1 = chrono::steady_clock::now().time_since_epoch().count();
static const uint64_t FIXED_RANDOM2 = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x.first + FIXED_RANDOM1) ^ splitmix64(x.second + FIXED_RANDOM2);
}
};
int n;
vector <int> x, y, r;
vector <int> _kill;
void init() {
cin >> n;
x.resize(n);
y.resize(n);
r.resize(n);
for (int i = 0; i < n; ++i) {
cin >> x[i] >> y[i] >> r[i];
}
}
bool inter(int i, int j) {
return (ll)(x[i] - x[j]) * (x[i] - x[j]) + (ll)(y[i] - y[j]) * (y[i] - y[j]) <= (ll)(r[i] + r[j]) * (r[i] + r[j]);
}
gp_hash_table <pair <int, int>, vector <int>, custom_hash> who;
void rebuild(int B) {
who.clear();
for (int i = 0; i < n; ++i) {
if (_kill[i] != -1) continue;
int xx = x[i] / B;
int yy = y[i] / B;
who[make_pair(xx, yy)].push_back(i);
}
}
void solve() {
_kill.resize(n, -1);
vector <int> idx(n);
iota(idx.begin(), idx.end(), 0);
sort(idx.begin(), idx.end(), [&] (int i, int j) {
if (r[i] != r[j]) return r[i] > r[j];
return i < j;
});
int uk = 0;
int B = 2e9 + 7;
while (true) {
while (uk < n && _kill[idx[uk]] != -1) ++uk;
if (uk == n) break;
int cur = idx[uk];
if ((r[cur] << 1) <= B) {
B = r[cur];
rebuild(B);
}
_kill[cur] = cur;
int xx = x[cur] / B;
int yy = y[cur] / B;
for (int cx = xx - 2; cx <= xx + 2; ++cx) {
for (int cy = yy - 2; cy <= yy + 2; ++cy) {
if (who.count(make_pair(cx, cy))) {
vector <int> nw;
for (auto j : who[make_pair(cx, cy)]) {
if (inter(cur, j)) {
_kill[j] = cur;
}
else nw.push_back(j);
}
who[make_pair(cx, cy)] = nw;
}
}
}
}
for (int i = 0; i < n; ++i) {
cout << _kill[i] + 1 << ' ';
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.setf(ios::fixed); cout.precision(20);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
init();
solve();
}
Compilation message
circle_selection.cpp: In function 'void solve()':
circle_selection.cpp:80:25: error: 'class __gnu_pbds::gp_hash_table<std::pair<int, int>, std::vector<int>, custom_hash>' has no member named 'count'
if (who.count(make_pair(cx, cy))) {
^~~~~
