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 v vector
#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
struct Circle{
ll x, y, r, i;
};
int N;
v<Circle> C;
bool compC(Circle& a, Circle& b){
if(a.r==b.r) return a.i<b.i;
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;
}
v<ll> eBy;
void sub4(){
map<ii, v<ll>> grid;
for(int i=0; i<N; i++){
C[i].x+=1e9;
C[i].y+=1e9;
grid[{C[i].x/C[i].r, C[i].y/C[i].r}].push_back(i);
}
for(int i=0; i<N; i++){
Circle& cur = C[i];
if(eBy[cur.i]!=-1) continue;
for(ll x=cur.x/cur.r - 2; x<=cur.x/cur.r+2; x++){
for(ll y=cur.y/cur.r-2; y<=cur.y/cur.r+2; y++){
if(grid.find({x,y})==grid.end()) continue;
for(ll c:grid[{x,y}]){
if(eBy[C[c].i]==-1 && isect(C[c],cur)) eBy[C[c].i] = cur.i;
}
}
}
}
}
int main(){
cin>>N;
bool s2 = true;
bool s4 = true;
for(int i=0; i<N; i++){
ll x,y,r;
cin>>x>>y>>r;
C.push_back({x,y,r,i});
s2 = s2 && y==0;
s4 = s4 && r==C[0].r;
}
sort(C.begin(), C.end(), compC);
eBy = v<ll>(N,-1);
sub4();
for(int i:eBy) cout<<i+1<<" ";
cout<<endl;
}
# | 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... |