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>
#define int long long
using namespace std;
const int nmax=3e5+42;
struct circle
{
int x,y,r,id;
};
int n;
circle inp[nmax],sorted_inp[nmax];
bool touch(circle a,circle b)
{
long long d=1LL*(a.x-b.x)*(a.x-b.x)+1LL*(a.y-b.y)*(a.y-b.y);
long long mx=a.r+b.r;
mx=mx*mx;
return d<=mx;
}
bool cmp(circle a,circle b)
{
if(a.r!=b.r)return a.r>b.r;
return a.id<b.id;
}
int outp[nmax];
set< pair<int/*y*/,int/*id*/> > tree[nmax*4];
void update(int node,int l,int r,int pos,circle cur)
{
//cout<<node<<" -> "<<cur.y<<" "<<cur.id<<endl;
tree[node].insert({cur.y,cur.id});
if(l==r)return;
int av=(l+r)/2;
if(pos<=av)update(node*2,l,av,pos,cur);
else update(node*2+1,av+1,r,pos,cur);
}
void match(int node,int l,int r,int lq,int rq,circle cur)
{
if(tree[node].size()==0)return;
if(l==lq&&r==rq)
{
int y1=cur.y-2*cur.r;
int y2=cur.y+2*cur.r;
//cout<<y1<<" "<<y2<<endl;
set< pair<int/*y*/,int/*id*/> >::iterator it=tree[node].lower_bound({y1,0});
vector< pair<int/*y*/,int/*id*/> > to_pop={};
while(it!=tree[node].end())
{
pair<int/*y*/,int/*id*/> info=*it;
if(info.first>y2)break;
if(outp[info.second]==0)
{
if(touch(inp[info.second],cur))
{
//cout<<"touch "<<info.second<<" "<<cur.id<<" "<<endl;
outp[info.second]=cur.id;
}
}
if(outp[info.second])to_pop.push_back(info);
it++;
}
for(auto k:to_pop)
tree[node].erase(k);
}
int av=(l+r)/2;
if(lq<=av)match(node*2,l,av,lq,min(av,rq),cur);
if(av<rq)match(node*2+1,av+1,r,max(av+1,lq),rq,cur);
}
int help_x[nmax];
void push(int which)
{
outp[sorted_inp[which].id]=sorted_inp[which].id;
int x1=sorted_inp[which].x-2*sorted_inp[which].r;
int x2=sorted_inp[which].x+2*sorted_inp[which].r;
int le=lower_bound(help_x+1,help_x+n+1,x1)-help_x;
int ri=upper_bound(help_x+1,help_x+n+1,x2)-help_x;
ri--;
//cout<<"le= "<<le<<" ri= "<<ri<<endl;
if(le>ri)return;
match(1,1,n,le,ri,sorted_inp[which]);
}
signed main()
{
scanf("%i",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld%lld%lld",&inp[i].x,&inp[i].y,&inp[i].r);
inp[i].id=i;
}
for(int i=1;i<=n;i++)sorted_inp[i]=inp[i];
sort(sorted_inp+1,sorted_inp+n+1,cmp);
for(int i=1;i<=n;i++)help_x[i]=sorted_inp[i].x;
sort(help_x+1,help_x+n+1);
for(int i=1;i<=n;i++)
{
int pos=lower_bound(help_x+1,help_x+n+1,sorted_inp[i].x)-help_x;
update(1,1,n,pos,sorted_inp[i]);
}
for(int i=1;i<=n;i++)
if(outp[sorted_inp[i].id]==0)
push(i);
for(int i=1;i<=n;i++)printf("%i ",outp[i]);printf("\n");
return 0;
}
Compilation message (stderr)
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:116:13: warning: format '%i' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
116 | scanf("%i",&n);
| ~^ ~~
| | |
| | long long int*
| int*
| %lli
circle_selection.cpp:142:35: warning: format '%i' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
142 | for(int i=1;i<=n;i++)printf("%i ",outp[i]);printf("\n");
| ~^ ~~~~~~~
| | |
| int long long int
| %lli
circle_selection.cpp:142:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
142 | for(int i=1;i<=n;i++)printf("%i ",outp[i]);printf("\n");
| ^~~
circle_selection.cpp:142:48: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
142 | for(int i=1;i<=n;i++)printf("%i ",outp[i]);printf("\n");
| ^~~~~~
circle_selection.cpp:116:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
116 | scanf("%i",&n);
| ~~~~~^~~~~~~~~
circle_selection.cpp:119:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
119 | scanf("%lld%lld%lld",&inp[i].x,&inp[i].y,&inp[i].r);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |