/**
* author : pham van sam
* created : 13 June 2023 (Tuesday)
**/
#include <bits/stdc++.h>
using namespace std;
using namespace chrono;
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
#define REP(i, n) for (int i = 0, _n = n; i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define FORE(it, s) for (__typeof(s.begin()) it = (s).begin(); it != (s).end(); ++it)
template <typename U, typename V> bool maximize(U &A, const V &B) { return (A < B) ? (A = B, true) : false; }
template <typename U, typename V> bool minimize(U &A, const V &B) { return (A > B) ? (A = B, true) : false; }
const int MAXN = 3e5 + 5;
int N, ans[MAXN], index[MAXN];
long long sqr(long long x) { return x * x; }
struct Circle_t {
int x, y, r; // coordinate and radius
Circle_t (int x = 0, int y = 0, int r = 0) : x(x), y(y), r(r) {}
bool intersect(const Circle_t &a) const {
return sqr(x - a.x) + sqr(y - a.y) <= sqr(r + a.r);
}
} a[MAXN];
const int MAX = 1e9, INF = 2e9 + 7;
unordered_map <long long, vector <int>> mp;
void rescaling_grid(int sz) {
mp.clear();
FOR(i, 1, N) if(ans[i] == 0) {
int x = a[i].x / sz, y = a[i].y / sz;
long long tmp = 1LL * x * INF + y;
mp[tmp].push_back(i);
}
}
void eliminator(long long pos, int u) {
if(!mp.count(pos)) return;
vector <int> &points = mp[pos];
for (int i = 0; i < (int) points.size(); ++i) {
if(a[points[i]].intersect(a[u])) {
ans[points[i]] = u;
swap(points[i--], points.back());
points.pop_back();
}
}
if(points.empty()) mp.erase(pos);
}
void process(void) {
cin >> N;
FOR(i, 1, N) {
cin >> a[i].x >> a[i].y >> a[i].r;
a[i].x += MAX;
a[i].y += MAX;
}
iota(index + 1, index + N + 1, 1);
sort(index + 1, index + N + 1, [&] (int i, int j) {
return (a[i].r > a[j].r || (a[i].r == a[j].r && i < j));
});
int rMax = 1e9;
FOR(i, 1, N) {
int u = index[i];
if(ans[u]) continue;
if(a[u].r < rMax / 2) {
rMax = a[u].r;
rescaling_grid(rMax);
}
FOR(cx, a[u].x / rMax - 2, a[u].x / rMax + 2) {
FOR(cy, a[u].y / rMax - 2, a[u].y / rMax + 2) {
eliminator(1LL * cx * INF + cy, u);
}
}
}
FOR(i, 1, N) cout << ans[i] << " \n"[i == N];
}
signed main() {
#define TASK "TASK"
if(fopen(TASK".inp", "r")) {
freopen(TASK".inp", "r", stdin);
freopen(TASK".out", "w", stdout);
}
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
auto start_time = steady_clock::now();
int test = 1;
// cin >> test;
for (int i = 1; i <= test; ++i) {
process();
// cout << '\n';
}
auto end_time = steady_clock::now();
cerr << "\nExecution time : " << duration_cast<milliseconds> (end_time - start_time).count() << "[ms]" << endl;
return (0 ^ 0);
}
Compilation message
circle_selection.cpp:24:29: error: 'int index [300005]' redeclared as different kind of entity
24 | int N, ans[MAXN], index[MAXN];
| ^
In file included from /usr/include/string.h:432,
from /usr/include/c++/10/cstring:42,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:48,
from circle_selection.cpp:6:
/usr/include/strings.h:61:1: note: previous declaration 'const char* index(const char*, int)'
61 | index (const char *__s, int __c) __THROW
| ^~~~~
circle_selection.cpp: In function 'void process()':
circle_selection.cpp:70:16: error: invalid operands of types '<unresolved overloaded function type>' and 'int' to binary 'operator+'
70 | iota(index + 1, index + N + 1, 1);
| ~~~~~~^~~
circle_selection.cpp:70:27: error: invalid operands of types '<unresolved overloaded function type>' and 'int' to binary 'operator+'
70 | iota(index + 1, index + N + 1, 1);
| ~~~~~~^~~
circle_selection.cpp:71:16: error: invalid operands of types '<unresolved overloaded function type>' and 'int' to binary 'operator+'
71 | sort(index + 1, index + N + 1, [&] (int i, int j) {
| ~~~~~~^~~
circle_selection.cpp:71:27: error: invalid operands of types '<unresolved overloaded function type>' and 'int' to binary 'operator+'
71 | sort(index + 1, index + N + 1, [&] (int i, int j) {
| ~~~~~~^~~
circle_selection.cpp:76:22: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
76 | int u = index[i];
| ^
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:95:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
95 | freopen(TASK".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:96:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
96 | freopen(TASK".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
