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 sub1(){
for(int i=0; i<N; i++){
if(eBy[C[i].i]!=-1) continue;
eBy[C[i].i] = C[i].i;
for(int j=i+1; j<N; j++){
if(eBy[C[j].i]==-1 && isect(C[i], C[j])){
eBy[C[j].i] = C[i].i;
}
}
}
}
void sub2(){
set<ii> pts;
for(int i=0; i<N; i++){
pts.insert(make_pair(C[i].x-C[i].r, i));
pts.insert(make_pair(C[i].x+C[i].r, i));
}
for(int i=0; i<N; i++){
if(eBy[C[i].i]!=-1) continue;
v<int> del;
auto it = pts.lower_bound(make_pair(C[i].x-C[i].r, -1));
while(it!=pts.end() && (*it).fi<=C[i].x+C[i].r){
del.push_back((*it).se);
it++;
}
for(int ind:del){
eBy[C[ind].i] = C[i].i;
pts.erase(make_pair(C[ind].x-C[ind].r, ind));
pts.erase(make_pair(C[ind].x+C[ind].r, ind));
}
}
}
void sub3(){
set<ii> xs;
set<ii> ys;
for(int i=0; i<N; i++){
ys.insert({C[i].y-C[i].r, i});
ys.insert({C[i].y+C[i].r, i});
eBy[i] = i;
}
for(ii y:ys){
ll x = C[y.se].x;
if(C[y.se].y+C[y.se].r==y.fi) xs.erase({x,y.se});
auto it = xs.lower_bound({x,-1});
if(it!=xs.end()){
ll ind = (*it).se;
if(isect(C[y.se], C[ind])){
ll e = (compC(C[y.se], C[ind]) ? y.se : ind);
eBy[C[y.se].i] = C[e].i;
eBy[C[ind].i] = C[e].i;
}
}
if(it!=xs.begin()){
it--;
ll ind = (*it).se;
if(isect(C[y.se], C[ind])){
ll e = (compC(C[y.se], C[ind]) ? y.se : ind);
eBy[C[y.se].i] = C[e].i;
eBy[C[ind].i] = C[e].i;
}
}
if(C[y.se].y-C[y.se].r == y.fi) xs.insert({x,y.se});
}
}
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;
}
}
}
}
}
void full(){
}
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... |