#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
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]);
}
map <pair <int, int>, vector <int>> 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.pusb_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:68:33: error: 'class std::vector<int>' has no member named 'pusb_back'; did you mean 'push_back'?
else nw.pusb_back(j);
^~~~~~~~~
push_back
