This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxN = 3e5 + 5;
struct Circle{
ll x, y, r, id;
} C[maxN];
int n;
bool compC (Circle& a, Circle& b){
if(a.r == b.r) return a.id < b.id;
return a.r > b.r;
}
bool isect(Circle& a, Circle& b){
ll dx = a.x - b.x;
ll dy = a.y - b.y;
ll r = a.r + b.r;
return dx * dx + dy * dy <= r * r;
}
int ans[maxN];
map<pair<ll, ll>, vector<int>> block;
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n;
cin >> n;
for(int i = 1; i <= n; i++){
cin >> C[i].x >> C[i].y >> C[i].r;
C[i].id = i;
}
sort(C + 1, C + n + 1, compC);
for (int i = 1; i <= n; i++){
C[i].x += 1e9;
C[i].y += 1e9;
block[{C[i].x / C[i].r, C[i].y / C[i].r}].push_back(i);
}
for (int i = 1; i <= n; i++){
Circle& curr = C[i];
if (ans[curr.id]) continue;
for (ll x = curr.x / curr.r - 2; x <= curr.x / curr.r + 2; x++){
for (ll y = curr.y / curr.r - 2; y <= curr.y / curr.r + 2; y++){
if (block.find({x,y}) == block.end()) continue;
for (ll idx: block[{x,y}]){
if(ans[C[idx].id] == 0 && isect(C[idx], curr)) ans[C[idx].id] = curr.id;
}
}
}
}
for (int i = 1; i <= n; i++)
cout << ans[i] << ' ';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |