#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/extc++.h>
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
using pii = pair<int, int>;
// template<typename T>
// using prior = priority_queue<T, vector<T>, greater<T>>;
// template<typename T>
// using Prior = priority_queue<T>;
#define X first
#define Y second
#define ALL(x) (x).begin(), (x).end()
#define eb emplace_back
#define pb push_back
#define fastIO() ios_base::sync_with_stdio(false), cin.tie(0)
const int INF = 0x7f7f7f7f;
const int maxn = 3E5 + 5;
int R;
struct Circle {
int x, y, r, id;
bool operator < (const Circle &rhs) const {
if (r == rhs.r) return id > rhs.id;
return r < rhs.r;
}
};
int32_t main() {
fastIO();
int n;
cin >> n;
Prior<Circle> pq;
vector<Circle> cir(n);
for (int i = 0; i < n; ++i) {
cin >> cir[i].x >> cir[i].y >> cir[i].r;
cir[i].id = i;
pq.push(cir[i]);
}
R = cir[0].r;
gp_hash_table<pii, set<int>> cid;
for (int i = 0; i < n; ++i) {
cid[{cir[i].x / R, cir[i].y / R}].insert(cir[i].id);
}
vector<int> ans(n, -1);
while (!pq.empty()) {
while (!pq.empty() and ans[pq.top().id] != -1) pq.pop();
if (pq.empty()) break;
int bx = cir[pq.top().id].x / R;
int by = cir[pq.top().id].y / R;
for (int i : {-2, -1, 0, 1, 2}) {
for (int j : {-2, -1, 0, 1, 2}) {
vector<int> tbe;
for (auto c : cid[{bx + i, by + j}]) {
int dx = abs(cir[pq.top().id].x - cir[c].x);
int dy = abs(cir[pq.top().id].y - cir[c].y);
int dr = cir[pq.top().id].r + cir[c].r;
// cout << dx << " " << dy << " " << dr << "\n";
if (dx*dx + dy*dy <= dr*dr) tbe.eb(c), ans[c] = pq.top().id;
}
for (auto x : tbe) cid[{bx + i, by + j}].erase(x);
}
}
}
for (int i = 0; i < n; ++i) cout << ans[i] + 1 << " \n"[i == n-1];
return 0;
}
Compilation message
circle_selection.cpp: In function 'int32_t main()':
circle_selection.cpp:40:5: error: 'Prior' was not declared in this scope
Prior<Circle> pq;
^~~~~
circle_selection.cpp:40:17: error: expected primary-expression before '>' token
Prior<Circle> pq;
^
circle_selection.cpp:40:19: error: 'pq' was not declared in this scope
Prior<Circle> pq;
^~
circle_selection.cpp:40:19: note: suggested alternative: 'pb'
Prior<Circle> pq;
^~
pb
circle_selection.cpp:49:5: error: 'gp_hash_table' was not declared in this scope
gp_hash_table<pii, set<int>> cid;
^~~~~~~~~~~~~
circle_selection.cpp:49:5: note: suggested alternative:
In file included from /usr/include/x86_64-linux-gnu/c++/7/bits/extc++.h:73:0,
from circle_selection.cpp:2:
/usr/include/c++/7/ext/pb_ds/assoc_container.hpp:368:9: note: '__gnu_pbds::gp_hash_table'
class gp_hash_table : public PB_DS_GP_HASH_BASE
^~~~~~~~~~~~~
circle_selection.cpp:49:22: error: expected primary-expression before ',' token
gp_hash_table<pii, set<int>> cid;
^
circle_selection.cpp:49:31: error: expected primary-expression before '>' token
gp_hash_table<pii, set<int>> cid;
^~
circle_selection.cpp:49:34: error: 'cid' was not declared in this scope
gp_hash_table<pii, set<int>> cid;
^~~
circle_selection.cpp:49:34: note: suggested alternative: 'cir'
gp_hash_table<pii, set<int>> cid;
^~~
cir
