제출 #77971

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
77971		autumn_eel	원 고르기 (APIO18_circle_selection)	C++14	100 / 100	859 ms	37428 KiB

circle_selection

#include<cmath>
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
typedef double db;
using namespace std;
 
const int N=300010;
const db inf=1e20,eps=1e-3,alpha=acos(-1)/3;
int n,rt,ans[N];
db x,y,r;
struct P{ db x,y,r; int id; }cur,a[N];
struct Tr{ int ls,rs; db x1,y1,x2,y2; P c; }T[N];
 
bool cmpx(const P &a,const P &b){ return a.x<b.x; }
bool cmpy(const P &a,const P &b){ return a.y<b.y; }
bool cmpr(const P &a,const P &b){ return (a.r==b.r) ? a.id<b.id : a.r>b.r; }
 
void F(int x,int y){
	T[x].x1=min(T[x].x1,T[y].x1); T[x].x2=max(T[x].x2,T[y].x2);
	T[x].y1=min(T[x].y1,T[y].y1); T[x].y2=max(T[x].y2,T[y].y2);
}
 
void upd(int x){
	if (ans[T[x].c.id]) T[x].x1=T[x].y1=inf,T[x].x2=T[x].y2=-inf;
	else{
		T[x].x1=T[x].c.x-T[x].c.r; T[x].x2=T[x].c.x+T[x].c.r;
		T[x].y1=T[x].c.y-T[x].c.r; T[x].y2=T[x].c.y+T[x].c.r;
	}
	if (T[x].ls) F(x,T[x].ls);
	if (T[x].rs) F(x,T[x].rs);
}
 
int build(int l,int r,int k){
	if (l>r) return 0;
	double minx=inf,miny=inf,maxx=-inf,maxy=-inf;
	for(int i=l;i<r+1;i++){
		minx=min(minx,a[i].x-a[i].r);
		miny=min(miny,a[i].y-a[i].r);
		maxx=max(maxx,a[i].x+a[i].r);
		maxy=max(maxy,a[i].y+a[i].r);
	}
	if(maxx-minx>maxy-miny)k=0;
	else k=1;
	int mid=(l+r)>>1; nth_element(a+l,a+mid,a+r+1,k?cmpy:cmpx);
	T[mid].c=a[mid];
	T[mid].ls=build(l,mid-1,k^1); T[mid].rs=build(mid+1,r,k^1);
	upd(mid); return mid;
}
 
db sqr(db x){ return x*x; }
bool Out(int x){ return (T[x].x2<cur.x-cur.r-eps) || (T[x].x1>cur.x+cur.r+eps) || (T[x].y2<cur.y-cur.r-eps) || (T[x].y1>cur.y+cur.r+eps); }
bool chk(P &a){ return sqr(a.x-cur.x)+sqr(a.y-cur.y)<=sqr(a.r+cur.r)+eps; }
 
void que(int x){
	if (Out(x)) return;
	if (!ans[T[x].c.id] && chk(T[x].c)) ans[T[x].c.id]=cur.id;
	if (T[x].ls) que(T[x].ls);
	if (T[x].rs) que(T[x].rs);
}
 
int main(){
	//~ freopen("apiob.in","r",stdin);
	//~ freopen("apiob.out","w",stdout);
	scanf("%d",&n);
	rep(i,1,n)
		scanf("%lf%lf%lf",&x,&y,&r),a[i]=(P){x,y,r,i};
	rt=build(1,n,0); sort(a+1,a+n+1,cmpr);
	rep(i,1,n) if (!ans[a[i].id]) ans[a[i].id]=a[i].id,cur=a[i],que(rt);
	rep(i,1,n) printf("%d ",ans[i]); puts("");
	return 0;
}
/*
#include<cmath>
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
typedef double db;
using namespace std;
 
const int N=300010;
const db inf=1e20,eps=1e-3,alpha=acos(-1)/3;
int n,rt,ans[N];
db x,y,r;
struct P{ db x,y,r; int id; }cur,a[N];
struct Tr{ int ls,rs; db x1,y1,x2,y2; P c; }T[N];
 
bool cmpx(const P &a,const P &b){ return a.x<b.x; }
bool cmpy(const P &a,const P &b){ return a.y<b.y; }
bool cmpr(const P &a,const P &b){ return (a.r==b.r) ? a.id<b.id : a.r>b.r; }
 
void F(int x,int y){
	T[x].x1=min(T[x].x1,T[y].x1); T[x].x2=max(T[x].x2,T[y].x2);
	T[x].y1=min(T[x].y1,T[y].y1); T[x].y2=max(T[x].y2,T[y].y2);
}
 
void upd(int x){
	if (ans[T[x].c.id]) T[x].x1=T[x].y1=inf,T[x].x2=T[x].y2=-inf;
	else{
		T[x].x1=T[x].c.x-T[x].c.r; T[x].x2=T[x].c.x+T[x].c.r;
		T[x].y1=T[x].c.y-T[x].c.r; T[x].y2=T[x].c.y+T[x].c.r;
	}
	if (T[x].ls) F(x,T[x].ls);
	if (T[x].rs) F(x,T[x].rs);
}
 
int build(int l,int r,int k){
	if (l>r) return 0;
	int mid=(l+r)>>1; nth_element(a+l,a+mid,a+r+1,k?cmpy:cmpx);
	T[mid].c=a[mid];
	T[mid].ls=build(l,mid-1,k^1); T[mid].rs=build(mid+1,r,k^1);
	upd(mid); return mid;
}
 
db sqr(db x){ return x*x; }
bool Out(int x){ return (T[x].x2<cur.x-cur.r-eps) || (T[x].x1>cur.x+cur.r+eps) || (T[x].y2<cur.y-cur.r-eps) || (T[x].y1>cur.y+cur.r+eps); }
bool chk(P &a){ return sqr(a.x-cur.x)+sqr(a.y-cur.y)<=sqr(a.r+cur.r)+eps; }
 
void que(int x){
	if (Out(x)) return;
	if (!ans[T[x].c.id] && chk(T[x].c)) ans[T[x].c.id]=cur.id;
	if (T[x].ls) que(T[x].ls);
	if (T[x].rs) que(T[x].rs);
}
 
int main(){
	//~ freopen("apiob.in","r",stdin);
	//~ freopen("apiob.out","w",stdout);
	scanf("%d",&n);
	rep(i,1,n)
		scanf("%lf%lf%lf",&x,&y,&r),a[i]=(P){x*cos(alpha)+y*sin(alpha),y*cos(alpha)-x*sin(alpha),r,i};
	rt=build(1,n,0); sort(a+1,a+n+1,cmpr);
	rep(i,1,n) if (!ans[a[i].id]) ans[a[i].id]=a[i].id,cur=a[i],que(rt);
	rep(i,1,n) printf("%d ",ans[i]); puts("");
	return 0;
}
#include<cmath>
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
typedef double db;
using namespace std;
 
const int N=300010;
const db inf=1e20,eps=1e-3,alpha=acos(-1)/3;
int n,rt,ans[N];
db x,y,r;
struct P{ db x,y,r; int id; }cur,a[N];
struct Tr{ int ls,rs; db x1,y1,x2,y2; P c; }T[N];
 
bool cmpx(const P &a,const P &b){ return a.x<b.x; }
bool cmpy(const P &a,const P &b){ return a.y<b.y; }
bool cmpr(const P &a,const P &b){ return (a.r==b.r) ? a.id<b.id : a.r>b.r; }
 
void F(int x,int y){
	T[x].x1=min(T[x].x1,T[y].x1); T[x].x2=max(T[x].x2,T[y].x2);
	T[x].y1=min(T[x].y1,T[y].y1); T[x].y2=max(T[x].y2,T[y].y2);
}
 
void upd(int x){
	if (ans[T[x].c.id]) T[x].x1=T[x].y1=inf,T[x].x2=T[x].y2=-inf;
	else{
		T[x].x1=T[x].c.x-T[x].c.r; T[x].x2=T[x].c.x+T[x].c.r;
		T[x].y1=T[x].c.y-T[x].c.r; T[x].y2=T[x].c.y+T[x].c.r;
	}
	if (T[x].ls) F(x,T[x].ls);
	if (T[x].rs) F(x,T[x].rs);
}
 
int build(int l,int r,int k){
	if (l>r) return 0;
	int mid=(l+r)>>1; nth_element(a+l,a+mid,a+r+1,k?cmpy:cmpx);
	T[mid].c=a[mid];
	T[mid].ls=build(l,mid-1,k^1); T[mid].rs=build(mid+1,r,k^1);
	upd(mid); return mid;
}
 
db sqr(db x){ return x*x; }
bool Out(int x){ return (T[x].x2<cur.x-cur.r-eps) || (T[x].x1>cur.x+cur.r+eps) || (T[x].y2<cur.y-cur.r-eps) || (T[x].y1>cur.y+cur.r+eps); }
bool chk(P &a){ return sqr(a.x-cur.x)+sqr(a.y-cur.y)<=sqr(a.r+cur.r)+eps; }
 
void que(int x){
	if (Out(x)) return;
	if (!ans[T[x].c.id] && chk(T[x].c)) ans[T[x].c.id]=cur.id;
	if (T[x].ls) que(T[x].ls);
	if (T[x].rs) que(T[x].rs);
}
 
int main(){
	//~ freopen("apiob.in","r",stdin);
	//~ freopen("apiob.out","w",stdout);
	scanf("%d",&n);
	rep(i,1,n)
		scanf("%lf%lf%lf",&x,&y,&r),a[i]=(P){x*cos(alpha)+y*sin(alpha),y*cos(alpha)-x*sin(alpha),r,i};
	rt=build(1,n,0); sort(a+1,a+n+1,cmpr);
	rep(i,1,n) if (!ans[a[i].id]) ans[a[i].id]=a[i].id,cur=a[i],que(rt);
	rep(i,1,n) printf("%d ",ans[i]); puts("");
	return 0;
}#include<cmath>
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
typedef double db;
using namespace std;
 
const int N=300010;
const db inf=1e20,eps=1e-3,alpha=acos(-1)/3;
int n,rt,ans[N];
db x,y,r;
struct P{ db x,y,r; int id; }cur,a[N];
struct Tr{ int ls,rs; db x1,y1,x2,y2; P c; }T[N];
 
bool cmpx(const P &a,const P &b){ return a.x<b.x; }
bool cmpy(const P &a,const P &b){ return a.y<b.y; }
bool cmpr(const P &a,const P &b){ return (a.r==b.r) ? a.id<b.id : a.r>b.r; }
 
void F(int x,int y){
	T[x].x1=min(T[x].x1,T[y].x1); T[x].x2=max(T[x].x2,T[y].x2);
	T[x].y1=min(T[x].y1,T[y].y1); T[x].y2=max(T[x].y2,T[y].y2);
}
 
void upd(int x){
	if (ans[T[x].c.id]) T[x].x1=T[x].y1=inf,T[x].x2=T[x].y2=-inf;
	else{
		T[x].x1=T[x].c.x-T[x].c.r; T[x].x2=T[x].c.x+T[x].c.r;
		T[x].y1=T[x].c.y-T[x].c.r; T[x].y2=T[x].c.y+T[x].c.r;
	}
	if (T[x].ls) F(x,T[x].ls);
	if (T[x].rs) F(x,T[x].rs);
}
 
int build(int l,int r,int k){
	if (l>r) return 0;
	int mid=(l+r)>>1; nth_element(a+l,a+mid,a+r+1,k?cmpy:cmpx);
	T[mid].c=a[mid];
	T[mid].ls=build(l,mid-1,k^1); T[mid].rs=build(mid+1,r,k^1);
	upd(mid); return mid;
}
 
db sqr(db x){ return x*x; }
bool Out(int x){ return (T[x].x2<cur.x-cur.r-eps) || (T[x].x1>cur.x+cur.r+eps) || (T[x].y2<cur.y-cur.r-eps) || (T[x].y1>cur.y+cur.r+eps); }
bool chk(P &a){ return sqr(a.x-cur.x)+sqr(a.y-cur.y)<=sqr(a.r+cur.r)+eps; }
 
void que(int x){
	if (Out(x)) return;
	if (!ans[T[x].c.id] && chk(T[x].c)) ans[T[x].c.id]=cur.id;
	if (T[x].ls) que(T[x].ls);
	if (T[x].rs) que(T[x].rs);
}
 
int main(){
	//~ freopen("apiob.in","r",stdin);
	//~ freopen("apiob.out","w",stdout);
	scanf("%d",&n);
	rep(i,1,n)
		scanf("%lf%lf%lf",&x,&y,&r),a[i]=(P){x*cos(alpha)+y*sin(alpha),y*cos(alpha)-x*sin(alpha),r,i};
	rt=build(1,n,0); sort(a+1,a+n+1,cmpr);
	rep(i,1,n) if (!ans[a[i].id]) ans[a[i].id]=a[i].id,cur=a[i],que(rt);
	rep(i,1,n) printf("%d ",ans[i]); puts("");
	return 0;
}#include<cmath>
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
typedef double db;
using namespace std;
 
const int N=300010;
const db inf=1e20,eps=1e-3,alpha=acos(-1)/3;
int n,rt,ans[N];
db x,y,r;
struct P{ db x,y,r; int id; }cur,a[N];
struct Tr{ int ls,rs; db x1,y1,x2,y2; P c; }T[N];
 
bool cmpx(const P &a,const P &b){ return a.x<b.x; }
bool cmpy(const P &a,const P &b){ return a.y<b.y; }
bool cmpr(const P &a,const P &b){ return (a.r==b.r) ? a.id<b.id : a.r>b.r; }
 
void F(int x,int y){
	T[x].x1=min(T[x].x1,T[y].x1); T[x].x2=max(T[x].x2,T[y].x2);
	T[x].y1=min(T[x].y1,T[y].y1); T[x].y2=max(T[x].y2,T[y].y2);
}
 
void upd(int x){
	if (ans[T[x].c.id]) T[x].x1=T[x].y1=inf,T[x].x2=T[x].y2=-inf;
	else{
		T[x].x1=T[x].c.x-T[x].c.r; T[x].x2=T[x].c.x+T[x].c.r;
		T[x].y1=T[x].c.y-T[x].c.r; T[x].y2=T[x].c.y+T[x].c.r;
	}
	if (T[x].ls) F(x,T[x].ls);
	if (T[x].rs) F(x,T[x].rs);
}
 
int build(int l,int r,int k){
	if (l>r) return 0;
	int mid=(l+r)>>1; nth_element(a+l,a+mid,a+r+1,k?cmpy:cmpx);
	T[mid].c=a[mid];
	T[mid].ls=build(l,mid-1,k^1); T[mid].rs=build(mid+1,r,k^1);
	upd(mid); return mid;
}
 
db sqr(db x){ return x*x; }
bool Out(int x){ return (T[x].x2<cur.x-cur.r-eps) || (T[x].x1>cur.x+cur.r+eps) || (T[x].y2<cur.y-cur.r-eps) || (T[x].y1>cur.y+cur.r+eps); }
bool chk(P &a){ return sqr(a.x-cur.x)+sqr(a.y-cur.y)<=sqr(a.r+cur.r)+eps; }
 
void que(int x){
	if (Out(x)) return;
	if (!ans[T[x].c.id] && chk(T[x].c)) ans[T[x].c.id]=cur.id;
	if (T[x].ls) que(T[x].ls);
	if (T[x].rs) que(T[x].rs);
}
 
int main(){
	//~ freopen("apiob.in","r",stdin);
	//~ freopen("apiob.out","w",stdout);
	scanf("%d",&n);
	rep(i,1,n)
		scanf("%lf%lf%lf",&x,&y,&r),a[i]=(P){x*cos(alpha)+y*sin(alpha),y*cos(alpha)-x*sin(alpha),r,i};
	rt=build(1,n,0); sort(a+1,a+n+1,cmpr);
	rep(i,1,n) if (!ans[a[i].id]) ans[a[i].id]=a[i].id,cur=a[i],que(rt);
	rep(i,1,n) printf("%d ",ans[i]); puts("");
	return 0;
}#include<cmath>
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
typedef double db;
using namespace std;
 
const int N=300010;
const db inf=1e20,eps=1e-3,alpha=acos(-1)/3;
int n,rt,ans[N];
db x,y,r;
struct P{ db x,y,r; int id; }cur,a[N];
struct Tr{ int ls,rs; db x1,y1,x2,y2; P c; }T[N];
 
bool cmpx(const P &a,const P &b){ return a.x<b.x; }
bool cmpy(const P &a,const P &b){ return a.y<b.y; }
bool cmpr(const P &a,const P &b){ return (a.r==b.r) ? a.id<b.id : a.r>b.r; }
 
void F(int x,int y){
	T[x].x1=min(T[x].x1,T[y].x1); T[x].x2=max(T[x].x2,T[y].x2);
	T[x].y1=min(T[x].y1,T[y].y1); T[x].y2=max(T[x].y2,T[y].y2);
}
 
void upd(int x){
	if (ans[T[x].c.id]) T[x].x1=T[x].y1=inf,T[x].x2=T[x].y2=-inf;
	else{
		T[x].x1=T[x].c.x-T[x].c.r; T[x].x2=T[x].c.x+T[x].c.r;
		T[x].y1=T[x].c.y-T[x].c.r; T[x].y2=T[x].c.y+T[x].c.r;
	}
	if (T[x].ls) F(x,T[x].ls);
	if (T[x].rs) F(x,T[x].rs);
}
 
int build(int l,int r,int k){
	if (l>r) return 0;
	int mid=(l+r)>>1; nth_element(a+l,a+mid,a+r+1,k?cmpy:cmpx);
	T[mid].c=a[mid];
	T[mid].ls=build(l,mid-1,k^1); T[mid].rs=build(mid+1,r,k^1);
	upd(mid); return mid;
}
 
db sqr(db x){ return x*x; }
bool Out(int x){ return (T[x].x2<cur.x-cur.r-eps) || (T[x].x1>cur.x+cur.r+eps) || (T[x].y2<cur.y-cur.r-eps) || (T[x].y1>cur.y+cur.r+eps); }
bool chk(P &a){ return sqr(a.x-cur.x)+sqr(a.y-cur.y)<=sqr(a.r+cur.r)+eps; }
 
void que(int x){
	if (Out(x)) return;
	if (!ans[T[x].c.id] && chk(T[x].c)) ans[T[x].c.id]=cur.id;
	if (T[x].ls) que(T[x].ls);
	if (T[x].rs) que(T[x].rs);
}
 
int main(){
	//~ freopen("apiob.in","r",stdin);
	//~ freopen("apiob.out","w",stdout);
	scanf("%d",&n);
	rep(i,1,n)
		scanf("%lf%lf%lf",&x,&y,&r),a[i]=(P){x*cos(alpha)+y*sin(alpha),y*cos(alpha)-x*sin(alpha),r,i};
	rt=build(1,n,0); sort(a+1,a+n+1,cmpr);
	rep(i,1,n) if (!ans[a[i].id]) ans[a[i].id]=a[i].id,cur=a[i],que(rt);
	rep(i,1,n) printf("%d ",ans[i]); puts("");
	return 0;
}#include<cmath>
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
typedef double db;
using namespace std;
 
const int N=300010;
const db inf=1e20,eps=1e-3,alpha=acos(-1)/3;
int n,rt,ans[N];
db x,y,r;
struct P{ db x,y,r; int id; }cur,a[N];
struct Tr{ int ls,rs; db x1,y1,x2,y2; P c; }T[N];
 
bool cmpx(const P &a,const P &b){ return a.x<b.x; }
bool cmpy(const P &a,const P &b){ return a.y<b.y; }
bool cmpr(const P &a,const P &b){ return (a.r==b.r) ? a.id<b.id : a.r>b.r; }
 
void F(int x,int y){
	T[x].x1=min(T[x].x1,T[y].x1); T[x].x2=max(T[x].x2,T[y].x2);
	T[x].y1=min(T[x].y1,T[y].y1); T[x].y2=max(T[x].y2,T[y].y2);
}
 
void upd(int x){
	if (ans[T[x].c.id]) T[x].x1=T[x].y1=inf,T[x].x2=T[x].y2=-inf;
	else{
		T[x].x1=T[x].c.x-T[x].c.r; T[x].x2=T[x].c.x+T[x].c.r;
		T[x].y1=T[x].c.y-T[x].c.r; T[x].y2=T[x].c.y+T[x].c.r;
	}
	if (T[x].ls) F(x,T[x].ls);
	if (T[x].rs) F(x,T[x].rs);
}
 
int build(int l,int r,int k){
	if (l>r) return 0;
	int mid=(l+r)>>1; nth_element(a+l,a+mid,a+r+1,k?cmpy:cmpx);
	T[mid].c=a[mid];
	T[mid].ls=build(l,mid-1,k^1); T[mid].rs=build(mid+1,r,k^1);
	upd(mid); return mid;
}
 
db sqr(db x){ return x*x; }
bool Out(int x){ return (T[x].x2<cur.x-cur.r-eps) || (T[x].x1>cur.x+cur.r+eps) || (T[x].y2<cur.y-cur.r-eps) || (T[x].y1>cur.y+cur.r+eps); }
bool chk(P &a){ return sqr(a.x-cur.x)+sqr(a.y-cur.y)<=sqr(a.r+cur.r)+eps; }
 
void que(int x){
	if (Out(x)) return;
	if (!ans[T[x].c.id] && chk(T[x].c)) ans[T[x].c.id]=cur.id;
	if (T[x].ls) que(T[x].ls);
	if (T[x].rs) que(T[x].rs);
}
 
int main(){
	//~ freopen("apiob.in","r",stdin);
	//~ freopen("apiob.out","w",stdout);
	scanf("%d",&n);
	rep(i,1,n)
		scanf("%lf%lf%lf",&x,&y,&r),a[i]=(P){x*cos(alpha)+y*sin(alpha),y*cos(alpha)-x*sin(alpha),r,i};
	rt=build(1,n,0); sort(a+1,a+n+1,cmpr);
	rep(i,1,n) if (!ans[a[i].id]) ans[a[i].id]=a[i].id,cur=a[i],que(rt);
	rep(i,1,n) printf("%d ",ans[i]); puts("");
	return 0;
}#include<cmath>
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
typedef double db;
using namespace std;
 
const int N=300010;
const db inf=1e20,eps=1e-3,alpha=acos(-1)/3;
int n,rt,ans[N];
db x,y,r;
struct P{ db x,y,r; int id; }cur,a[N];
struct Tr{ int ls,rs; db x1,y1,x2,y2; P c; }T[N];
 
bool cmpx(const P &a,const P &b){ return a.x<b.x; }
bool cmpy(const P &a,const P &b){ return a.y<b.y; }
bool cmpr(const P &a,const P &b){ return (a.r==b.r) ? a.id<b.id : a.r>b.r; }
 
void F(int x,int y){
	T[x].x1=min(T[x].x1,T[y].x1); T[x].x2=max(T[x].x2,T[y].x2);
	T[x].y1=min(T[x].y1,T[y].y1); T[x].y2=max(T[x].y2,T[y].y2);
}
 
void upd(int x){
	if (ans[T[x].c.id]) T[x].x1=T[x].y1=inf,T[x].x2=T[x].y2=-inf;
	else{
		T[x].x1=T[x].c.x-T[x].c.r; T[x].x2=T[x].c.x+T[x].c.r;
		T[x].y1=T[x].c.y-T[x].c.r; T[x].y2=T[x].c.y+T[x].c.r;
	}
	if (T[x].ls) F(x,T[x].ls);
	if (T[x].rs) F(x,T[x].rs);
}
 
int build(int l,int r,int k){
	if (l>r) return 0;
	int mid=(l+r)>>1; nth_element(a+l,a+mid,a+r+1,k?cmpy:cmpx);
	T[mid].c=a[mid];
	T[mid].ls=build(l,mid-1,k^1); T[mid].rs=build(mid+1,r,k^1);
	upd(mid); return mid;
}
 
db sqr(db x){ return x*x; }
bool Out(int x){ return (T[x].x2<cur.x-cur.r-eps) || (T[x].x1>cur.x+cur.r+eps) || (T[x].y2<cur.y-cur.r-eps) || (T[x].y1>cur.y+cur.r+eps); }
bool chk(P &a){ return sqr(a.x-cur.x)+sqr(a.y-cur.y)<=sqr(a.r+cur.r)+eps; }
 
void que(int x){
	if (Out(x)) return;
	if (!ans[T[x].c.id] && chk(T[x].c)) ans[T[x].c.id]=cur.id;
	if (T[x].ls) que(T[x].ls);
	if (T[x].rs) que(T[x].rs);
}
 
int main(){
	//~ freopen("apiob.in","r",stdin);
	//~ freopen("apiob.out","w",stdout);
	scanf("%d",&n);
	rep(i,1,n)
		scanf("%lf%lf%lf",&x,&y,&r),a[i]=(P){x*cos(alpha)+y*sin(alpha),y*cos(alpha)-x*sin(alpha),r,i};
	rt=build(1,n,0); sort(a+1,a+n+1,cmpr);
	rep(i,1,n) if (!ans[a[i].id]) ans[a[i].id]=a[i].id,cur=a[i],que(rt);
	rep(i,1,n) printf("%d ",ans[i]); puts("");
	return 0;
}#include<cmath>
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
typedef double db;
using namespace std;
 
const int N=300010;
const db inf=1e20,eps=1e-3,alpha=acos(-1)/3;
int n,rt,ans[N];
db x,y,r;
struct P{ db x,y,r; int id; }cur,a[N];
struct Tr{ int ls,rs; db x1,y1,x2,y2; P c; }T[N];
 
bool cmpx(const P &a,const P &b){ return a.x<b.x; }
bool cmpy(const P &a,const P &b){ return a.y<b.y; }
bool cmpr(const P &a,const P &b){ return (a.r==b.r) ? a.id<b.id : a.r>b.r; }
 
void F(int x,int y){
	T[x].x1=min(T[x].x1,T[y].x1); T[x].x2=max(T[x].x2,T[y].x2);
	T[x].y1=min(T[x].y1,T[y].y1); T[x].y2=max(T[x].y2,T[y].y2);
}
 
void upd(int x){
	if (ans[T[x].c.id]) T[x].x1=T[x].y1=inf,T[x].x2=T[x].y2=-inf;
	else{
		T[x].x1=T[x].c.x-T[x].c.r; T[x].x2=T[x].c.x+T[x].c.r;
		T[x].y1=T[x].c.y-T[x].c.r; T[x].y2=T[x].c.y+T[x].c.r;
	}
	if (T[x].ls) F(x,T[x].ls);
	if (T[x].rs) F(x,T[x].rs);
}
 
int build(int l,int r,int k){
	if (l>r) return 0;
	int mid=(l+r)>>1; nth_element(a+l,a+mid,a+r+1,k?cmpy:cmpx);
	T[mid].c=a[mid];
	T[mid].ls=build(l,mid-1,k^1); T[mid].rs=build(mid+1,r,k^1);
	upd(mid); return mid;
}
 
db sqr(db x){ return x*x; }
bool Out(int x){ return (T[x].x2<cur.x-cur.r-eps) || (T[x].x1>cur.x+cur.r+eps) || (T[x].y2<cur.y-cur.r-eps) || (T[x].y1>cur.y+cur.r+eps); }
bool chk(P &a){ return sqr(a.x-cur.x)+sqr(a.y-cur.y)<=sqr(a.r+cur.r)+eps; }
 
void que(int x){
	if (Out(x)) return;
	if (!ans[T[x].c.id] && chk(T[x].c)) ans[T[x].c.id]=cur.id;
	if (T[x].ls) que(T[x].ls);
	if (T[x].rs) que(T[x].rs);
}
 
int main(){
	//~ freopen("apiob.in","r",stdin);
	//~ freopen("apiob.out","w",stdout);
	scanf("%d",&n);
	rep(i,1,n)
		scanf("%lf%lf%lf",&x,&y,&r),a[i]=(P){x*cos(alpha)+y*sin(alpha),y*cos(alpha)-x*sin(alpha),r,i};
	rt=build(1,n,0); sort(a+1,a+n+1,cmpr);
	rep(i,1,n) if (!ans[a[i].id]) ans[a[i].id]=a[i].id,cur=a[i],que(rt);
	rep(i,1,n) printf("%d ",ans[i]); puts("");
	return 0;
}#include<cmath>
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
typedef double db;
using namespace std;
 
const int N=300010;
const db inf=1e20,eps=1e-3,alpha=acos(-1)/3;
int n,rt,ans[N];
db x,y,r;
struct P{ db x,y,r; int id; }cur,a[N];
struct Tr{ int ls,rs; db x1,y1,x2,y2; P c; }T[N];
 
bool cmpx(const P &a,const P &b){ return a.x<b.x; }
bool cmpy(const P &a,const P &b){ return a.y<b.y; }
bool cmpr(const P &a,const P &b){ return (a.r==b.r) ? a.id<b.id : a.r>b.r; }
 
void F(int x,int y){
	T[x].x1=min(T[x].x1,T[y].x1); T[x].x2=max(T[x].x2,T[y].x2);
	T[x].y1=min(T[x].y1,T[y].y1); T[x].y2=max(T[x].y2,T[y].y2);
}
 
void upd(int x){
	if (ans[T[x].c.id]) T[x].x1=T[x].y1=inf,T[x].x2=T[x].y2=-inf;
	else{
		T[x].x1=T[x].c.x-T[x].c.r; T[x].x2=T[x].c.x+T[x].c.r;
		T[x].y1=T[x].c.y-T[x].c.r; T[x].y2=T[x].c.y+T[x].c.r;
	}
	if (T[x].ls) F(x,T[x].ls);
	if (T[x].rs) F(x,T[x].rs);
}
 
int build(int l,int r,int k){
	if (l>r) return 0;
	int mid=(l+r)>>1; nth_element(a+l,a+mid,a+r+1,k?cmpy:cmpx);
	T[mid].c=a[mid];
	T[mid].ls=build(l,mid-1,k^1); T[mid].rs=build(mid+1,r,k^1);
	upd(mid); return mid;
}
 
db sqr(db x){ return x*x; }
bool Out(int x){ return (T[x].x2<cur.x-cur.r-eps) || (T[x].x1>cur.x+cur.r+eps) || (T[x].y2<cur.y-cur.r-eps) || (T[x].y1>cur.y+cur.r+eps); }
bool chk(P &a){ return sqr(a.x-cur.x)+sqr(a.y-cur.y)<=sqr(a.r+cur.r)+eps; }
 
void que(int x){
	if (Out(x)) return;
	if (!ans[T[x].c.id] && chk(T[x].c)) ans[T[x].c.id]=cur.id;
	if (T[x].ls) que(T[x].ls);
	if (T[x].rs) que(T[x].rs);
}
 
int main(){
	//~ freopen("apiob.in","r",stdin);
	//~ freopen("apiob.out","w",stdout);
	scanf("%d",&n);
	rep(i,1,n)
		scanf("%lf%lf%lf",&x,&y,&r),a[i]=(P){x*cos(alpha)+y*sin(alpha),y*cos(alpha)-x*sin(alpha),r,i};
	rt=build(1,n,0); sort(a+1,a+n+1,cmpr);
	rep(i,1,n) if (!ans[a[i].id]) ans[a[i].id]=a[i].id,cur=a[i],que(rt);
	rep(i,1,n) printf("%d ",ans[i]); puts("");
	return 0;
}#include<cmath>
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
typedef double db;
using namespace std;
 
const int N=300010;
const db inf=1e20,eps=1e-3,alpha=acos(-1)/3;
int n,rt,ans[N];
db x,y,r;
struct P{ db x,y,r; int id; }cur,a[N];
struct Tr{ int ls,rs; db x1,y1,x2,y2; P c; }T[N];
 
bool cmpx(const P &a,const P &b){ return a.x<b.x; }
bool cmpy(const P &a,const P &b){ return a.y<b.y; }
bool cmpr(const P &a,const P &b){ return (a.r==b.r) ? a.id<b.id : a.r>b.r; }
 
void F(int x,int y){
	T[x].x1=min(T[x].x1,T[y].x1); T[x].x2=max(T[x].x2,T[y].x2);
	T[x].y1=min(T[x].y1,T[y].y1); T[x].y2=max(T[x].y2,T[y].y2);
}
 
void upd(int x){
	if (ans[T[x].c.id]) T[x].x1=T[x].y1=inf,T[x].x2=T[x].y2=-inf;
	else{
		T[x].x1=T[x].c.x-T[x].c.r; T[x].x2=T[x].c.x+T[x].c.r;
		T[x].y1=T[x].c.y-T[x].c.r; T[x].y2=T[x].c.y+T[x].c.r;
	}
	if (T[x].ls) F(x,T[x].ls);
	if (T[x].rs) F(x,T[x].rs);
}
 
int build(int l,int r,int k){
	if (l>r) return 0;
	int mid=(l+r)>>1; nth_element(a+l,a+mid,a+r+1,k?cmpy:cmpx);
	T[mid].c=a[mid];
	T[mid].ls=build(l,mid-1,k^1); T[mid].rs=build(mid+1,r,k^1);
	upd(mid); return mid;
}
 
db sqr(db x){ return x*x; }
bool Out(int x){ return (T[x].x2<cur.x-cur.r-eps) || (T[x].x1>cur.x+cur.r+eps) || (T[x].y2<cur.y-cur.r-eps) || (T[x].y1>cur.y+cur.r+eps); }
bool chk(P &a){ return sqr(a.x-cur.x)+sqr(a.y-cur.y)<=sqr(a.r+cur.r)+eps; }
 
void que(int x){
	if (Out(x)) return;
	if (!ans[T[x].c.id] && chk(T[x].c)) ans[T[x].c.id]=cur.id;
	if (T[x].ls) que(T[x].ls);
	if (T[x].rs) que(T[x].rs);
}
 
int main(){
	//~ freopen("apiob.in","r",stdin);
	//~ freopen("apiob.out","w",stdout);
	scanf("%d",&n);
	rep(i,1,n)
		scanf("%lf%lf%lf",&x,&y,&r),a[i]=(P){x*cos(alpha)+y*sin(alpha),y*cos(alpha)-x*sin(alpha),r,i};
	rt=build(1,n,0); sort(a+1,a+n+1,cmpr);
	rep(i,1,n) if (!ans[a[i].id]) ans[a[i].id]=a[i].id,cur=a[i],que(rt);
	rep(i,1,n) printf("%d ",ans[i]); puts("");
	return 0;
}#include<cmath>
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
typedef double db;
using namespace std;
 
const int N=300010;
const db inf=1e20,eps=1e-3,alpha=acos(-1)/3;
int n,rt,ans[N];
db x,y,r;
struct P{ db x,y,r; int id; }cur,a[N];
struct Tr{ int ls,rs; db x1,y1,x2,y2; P c; }T[N];
 
bool cmpx(const P &a,const P &b){ return a.x<b.x; }
bool cmpy(const P &a,const P &b){ return a.y<b.y; }
bool cmpr(const P &a,const P &b){ return (a.r==b.r) ? a.id<b.id : a.r>b.r; }
 
void F(int x,int y){
	T[x].x1=min(T[x].x1,T[y].x1); T[x].x2=max(T[x].x2,T[y].x2);
	T[x].y1=min(T[x].y1,T[y].y1); T[x].y2=max(T[x].y2,T[y].y2);
}
 
void upd(int x){
	if (ans[T[x].c.id]) T[x].x1=T[x].y1=inf,T[x].x2=T[x].y2=-inf;
	else{
		T[x].x1=T[x].c.x-T[x].c.r; T[x].x2=T[x].c.x+T[x].c.r;
		T[x].y1=T[x].c.y-T[x].c.r; T[x].y2=T[x].c.y+T[x].c.r;
	}
	if (T[x].ls) F(x,T[x].ls);
	if (T[x].rs) F(x,T[x].rs);
}
 
int build(int l,int r,int k){
	if (l>r) return 0;
	int mid=(l+r)>>1; nth_element(a+l,a+mid,a+r+1,k?cmpy:cmpx);
	T[mid].c=a[mid];
	T[mid].ls=build(l,mid-1,k^1); T[mid].rs=build(mid+1,r,k^1);
	upd(mid); return mid;
}
 
db sqr(db x){ return x*x; }
bool Out(int x){ return (T[x].x2<cur.x-cur.r-eps) || (T[x].x1>cur.x+cur.r+eps) || (T[x].y2<cur.y-cur.r-eps) || (T[x].y1>cur.y+cur.r+eps); }
bool chk(P &a){ return sqr(a.x-cur.x)+sqr(a.y-cur.y)<=sqr(a.r+cur.r)+eps; }
 
void que(int x){
	if (Out(x)) return;
	if (!ans[T[x].c.id] && chk(T[x].c)) ans[T[x].c.id]=cur.id;
	if (T[x].ls) que(T[x].ls);
	if (T[x].rs) que(T[x].rs);
}
 
int main(){
	//~ freopen("apiob.in","r",stdin);
	//~ freopen("apiob.out","w",stdout);
	scanf("%d",&n);
	rep(i,1,n)
		scanf("%lf%lf%lf",&x,&y,&r),a[i]=(P){x*cos(alpha)+y*sin(alpha),y*cos(alpha)-x*sin(alpha),r,i};
	rt=build(1,n,0); sort(a+1,a+n+1,cmpr);
	rep(i,1,n) if (!ans[a[i].id]) ans[a[i].id]=a[i].id,cur=a[i],que(rt);
	rep(i,1,n) printf("%d ",ans[i]); puts("");
	return 0;
}#include<cmath>
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
typedef double db;
using namespace std;
 
const int N=300010;
const db inf=1e20,eps=1e-3,alpha=acos(-1)/3;
int n,rt,ans[N];
db x,y,r;
struct P{ db x,y,r; int id; }cur,a[N];
struct Tr{ int ls,rs; db x1,y1,x2,y2; P c; }T[N];
 
bool cmpx(const P &a,const P &b){ return a.x<b.x; }
bool cmpy(const P &a,const P &b){ return a.y<b.y; }
bool cmpr(const P &a,const P &b){ return (a.r==b.r) ? a.id<b.id : a.r>b.r; }
 
void F(int x,int y){
	T[x].x1=min(T[x].x1,T[y].x1); T[x].x2=max(T[x].x2,T[y].x2);
	T[x].y1=min(T[x].y1,T[y].y1); T[x].y2=max(T[x].y2,T[y].y2);
}
 
void upd(int x){
	if (ans[T[x].c.id]) T[x].x1=T[x].y1=inf,T[x].x2=T[x].y2=-inf;
	else{
		T[x].x1=T[x].c.x-T[x].c.r; T[x].x2=T[x].c.x+T[x].c.r;
		T[x].y1=T[x].c.y-T[x].c.r; T[x].y2=T[x].c.y+T[x].c.r;
	}
	if (T[x].ls) F(x,T[x].ls);
	if (T[x].rs) F(x,T[x].rs);
}
 
int build(int l,int r,int k){
	if (l>r) return 0;
	int mid=(l+r)>>1; nth_element(a+l,a+mid,a+r+1,k?cmpy:cmpx);
	T[mid].c=a[mid];
	T[mid].ls=build(l,mid-1,k^1); T[mid].rs=build(mid+1,r,k^1);
	upd(mid); return mid;
}
 
db sqr(db x){ return x*x; }
bool Out(int x){ return (T[x].x2<cur.x-cur.r-eps) || (T[x].x1>cur.x+cur.r+eps) || (T[x].y2<cur.y-cur.r-eps) || (T[x].y1>cur.y+cur.r+eps); }
bool chk(P &a){ return sqr(a.x-cur.x)+sqr(a.y-cur.y)<=sqr(a.r+cur.r)+eps; }
 
void que(int x){
	if (Out(x)) return;
	if (!ans[T[x].c.id] && chk(T[x].c)) ans[T[x].c.id]=cur.id;
	if (T[x].ls) que(T[x].ls);
	if (T[x].rs) que(T[x].rs);
}
 
int main(){
	//~ freopen("apiob.in","r",stdin);
	//~ freopen("apiob.out","w",stdout);
	scanf("%d",&n);
	rep(i,1,n)
		scanf("%lf%lf%lf",&x,&y,&r),a[i]=(P){x*cos(alpha)+y*sin(alpha),y*cos(alpha)-x*sin(alpha),r,i};
	rt=build(1,n,0); sort(a+1,a+n+1,cmpr);
	rep(i,1,n) if (!ans[a[i].id]) ans[a[i].id]=a[i].id,cur=a[i],que(rt);
	rep(i,1,n) printf("%d ",ans[i]); puts("");
	return 0;
}#include<cmath>
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
typedef double db;
using namespace std;
 
const int N=300010;
const db inf=1e20,eps=1e-3,alpha=acos(-1)/3;
int n,rt,ans[N];
db x,y,r;
struct P{ db x,y,r; int id; }cur,a[N];
struct Tr{ int ls,rs; db x1,y1,x2,y2; P c; }T[N];
 
bool cmpx(const P &a,const P &b){ return a.x<b.x; }
bool cmpy(const P &a,const P &b){ return a.y<b.y; }
bool cmpr(const P &a,const P &b){ return (a.r==b.r) ? a.id<b.id : a.r>b.r; }
 
void F(int x,int y){
	T[x].x1=min(T[x].x1,T[y].x1); T[x].x2=max(T[x].x2,T[y].x2);
	T[x].y1=min(T[x].y1,T[y].y1); T[x].y2=max(T[x].y2,T[y].y2);
}
 
void upd(int x){
	if (ans[T[x].c.id]) T[x].x1=T[x].y1=inf,T[x].x2=T[x].y2=-inf;
	else{
		T[x].x1=T[x].c.x-T[x].c.r; T[x].x2=T[x].c.x+T[x].c.r;
		T[x].y1=T[x].c.y-T[x].c.r; T[x].y2=T[x].c.y+T[x].c.r;
	}
	if (T[x].ls) F(x,T[x].ls);
	if (T[x].rs) F(x,T[x].rs);
}
 
int build(int l,int r,int k){
	if (l>r) return 0;
	int mid=(l+r)>>1; nth_element(a+l,a+mid,a+r+1,k?cmpy:cmpx);
	T[mid].c=a[mid];
	T[mid].ls=build(l,mid-1,k^1); T[mid].rs=build(mid+1,r,k^1);
	upd(mid); return mid;
}
 
db sqr(db x){ return x*x; }
bool Out(int x){ return (T[x].x2<cur.x-cur.r-eps) || (T[x].x1>cur.x+cur.r+eps) || (T[x].y2<cur.y-cur.r-eps) || (T[x].y1>cur.y+cur.r+eps); }
bool chk(P &a){ return sqr(a.x-cur.x)+sqr(a.y-cur.y)<=sqr(a.r+cur.r)+eps; }
 
void que(int x){
	if (Out(x)) return;
	if (!ans[T[x].c.id] && chk(T[x].c)) ans[T[x].c.id]=cur.id;
	if (T[x].ls) que(T[x].ls);
	if (T[x].rs) que(T[x].rs);
}
 
int main(){
	//~ freopen("apiob.in","r",stdin);
	//~ freopen("apiob.out","w",stdout);
	scanf("%d",&n);
	rep(i,1,n)
		scanf("%lf%lf%lf",&x,&y,&r),a[i]=(P){x*cos(alpha)+y*sin(alpha),y*cos(alpha)-x*sin(alpha),r,i};
	rt=build(1,n,0); sort(a+1,a+n+1,cmpr);
	rep(i,1,n) if (!ans[a[i].id]) ans[a[i].id]=a[i].id,cur=a[i],que(rt);
	rep(i,1,n) printf("%d ",ans[i]); puts("");
	return 0;
}*/

컴파일 시 표준 에러 (stderr) 메시지

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:4:20: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
 #define rep(i,l,r) for (int i=(l); i<=(r); i++)
                    ^
circle_selection.cpp:70:2: note: in expansion of macro 'rep'
  rep(i,1,n) printf("%d ",ans[i]); puts("");
  ^~~
circle_selection.cpp:70:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  rep(i,1,n) printf("%d ",ans[i]); puts("");
                                   ^~~~
circle_selection.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
circle_selection.cpp:67:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lf%lf%lf",&x,&y,&r),a[i]=(P){x,y,r,i};
   ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 30 / 30
• Subtask 6: 13 / 13