제출 #77734

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

circle_selection

#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define INF INT_MAX
using namespace std;
typedef long long ll;

int ans[400000];
struct Circle{
	int x,y,r;
	int id;
	int bbox[2][2];
	Circle(){}
	Circle(int x,int y,int r,int id):x(x),y(y),r(r),id(id){
		bbox[0][0]=x-r;bbox[0][1]=y-r;
		bbox[1][0]=x+r;bbox[1][1]=y+r;
	}
};
struct node{
	int bbox[2][2];
	node*l,*r;
	vector<Circle*>circle;
};
ll area(int bbox[2][2]){
	return (bbox[1][0]-bbox[0][0])*(ll)(bbox[1][1]-bbox[0][1]);
}
void init(int bbox[2][2]){
	bbox[0][0]=bbox[0][1]=INF;
	bbox[1][0]=bbox[1][1]=-INF;
}
void mergeAABB(int bbox[2][2],int bbox2[2][2],int result[2][2]){
	rep(i,2){
		result[0][i]=min(bbox[0][i],bbox2[0][i]);
		result[1][i]=max(bbox[1][i],bbox2[1][i]);
	}
}
void createAABB(vector<Circle*>&circle,int result[2][2]){
	init(result);
	for(auto&c:circle){
		mergeAABB(result,c->bbox,result);
	}
}
node bvh[400000];
int pointer=0;
 
#define t_tri 1
#define t_aabb 1
 
void setleaf(vector<Circle*>circle,node*n){
	n->l=n->r=NULL;
	n->circle=circle;
}
void build(vector<Circle*>&circle,node*n){
	createAABB(circle,n->bbox);
	ll Min=LLONG_MAX;
	int axis=-1,id=-1;
	rep(i,2){
		sort(circle.begin(),circle.end(),[&](auto a,auto b){
			if(i==0)return a->x<b->x;
			return a->y<b->y;
		});
		int box[2][2];init(box);
		vector<ll>s1(circle.size());
		rep(j,circle.size()){
			mergeAABB(box,circle[j]->bbox,box);
			s1[j]=area(box);
		}
		init(box);
		vector<ll>s2(circle.size());
		for(int j=circle.size()-1;j>=0;j--){
			mergeAABB(box,circle[j]->bbox,box);
			s2[j]=area(box);
		}
		for(int j=0;j+1<circle.size();j++){
			ll cost=(s1[j])*(j+1)+(s2[j+1])*(circle.size()-j-1);
			if(Min>cost){
				Min=cost;
				axis=i;id=j;
			}
		}
	}
	if(axis==-1||t_tri*circle.size()<2*t_aabb+Min*t_tri/(double)area(n->bbox)){
		setleaf(circle,n);
	}
	else{
		sort(circle.begin(),circle.end(),[&](auto a,auto b){
			if(axis==0)return a->x<b->x;
			return a->y<b->y;
		});
		n->l=&bvh[pointer++];
		n->r=&bvh[pointer++];
		vector<Circle*>left(circle.begin(),circle.begin()+id+1);
		vector<Circle*>right(circle.begin()+id+1,circle.end());
		build(left,n->l);
		build(right,n->r);
	}
}
void dfs_bvh(node*n,int depth){
	if(depth==3){
		cout<<"(minx,miny),(maxx,maxy) = "<<"("<<n->bbox[0][0]<<","<<n->bbox[0][1]<<")"<<","<<"("<<n->bbox[1][0]<<","<<n->bbox[1][1]<<")"<<endl;
	}
	if(n->l)dfs_bvh(n->l,depth+1);
	if(n->r)dfs_bvh(n->r,depth+1);
}
inline bool intersect(Circle*c1,Circle*c2){
	return (c1->x-c2->x)*(ll)(c1->x-c2->x)+(c1->y-c2->y)*(ll)(c1->y-c2->y)
			<=(c1->r+c2->r)*(ll)(c1->r+c2->r);
}
inline bool intersect(int bbox1[2][2],int bbox2[2][2]){
	if(bbox1[1][0]<bbox2[0][0]||bbox2[1][0]<bbox1[0][0]||bbox1[1][1]<bbox2[0][1]||bbox2[1][1]<bbox1[0][1])return false;
	return true;
}
inline bool intersect(Circle*c,int bbox[2][2]){
	if(!intersect(c->bbox,bbox))return false;
	if(bbox[0][0]<=c->x&&c->x<=bbox[1][0]&&bbox[0][1]<=c->y&&c->y<=bbox[1][1])return true;
	if(abs(bbox[0][0]-c->x)<=c->r&&bbox[0][1]<=c->y&&c->y<=bbox[1][1])return true;
	if(abs(bbox[1][0]-c->x)<=c->r&&bbox[0][1]<=c->y&&c->y<=bbox[1][1])return true;
	if(abs(bbox[0][1]-c->y)<=c->r&&bbox[0][0]<=c->x&&c->x<=bbox[1][0])return true;
	if(abs(bbox[1][1]-c->y)<=c->r&&bbox[0][0]<=c->x&&c->x<=bbox[1][0])return true;
	rep(i,2)rep(j,2){
		if((bbox[i][0]-c->x)*(ll)(bbox[i][0]-c->x)+(bbox[j][1]-c->y)*(ll)(bbox[j][1]-c->y)
			<=(c->r)*(ll)(c->r))return true;
	}
	return false;
}
node*intersect(node*n,Circle*c){
	if(!intersect(c,n->bbox))return n;
	if(n->l){
		auto l=intersect(n->l,c);
		auto r=intersect(n->r,c);
		if(l==NULL&&r==NULL)return NULL;
		if(l==NULL)return r;
		if(r==NULL)return l;
		n->l=l;n->r=r;
		init(n->bbox);
		mergeAABB(l->bbox,r->bbox,n->bbox);
		return n;
	}
	else{
		auto&circle=n->circle;
		vector<Circle*>res;
		rep(i,circle.size()){
			if(intersect(circle[i],c)){
				ans[circle[i]->id]=c->id;
			}
			else{
				res.push_back(circle[i]);
			}
		}
		if(res.empty())return NULL;
		circle=res;
		createAABB(circle,n->bbox);
		return n;
	}
}

Circle c[400000];
int main(){
	int n;scanf("%d",&n);
	vector<Circle*>circle;
	rep(i,n){
		int x,y,r;scanf("%d%d%d",&x,&y,&r);
		c[i]=Circle(x,y,r,i);
	}
	sort(c,c+n,[](auto a,auto b){
		if(a.r==b.r)return a.id<b.id;
		return a.r>b.r;
	});
	rep(i,n){
		circle.push_back(&c[i]);
	}
	node*root=&bvh[pointer++];
	build(circle,root);
	//~ dfs_bvh(root,0);
	memset(ans,-1,sizeof(ans));
	rep(i,n){
		if(ans[c[i].id]!=-1)continue;
		root=intersect(root,&c[i]);
		if(root==NULL)break;
	}
	rep(i,n){
		if(i)printf(" ");
		printf("%d",ans[i]+1);
	}
	puts("");
}

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

circle_selection.cpp: In function 'void build(std::vector<Circle*>&, node*)':
circle_selection.cpp:2:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,n)for(int i=0;i<(n);i++)
                              ^
circle_selection.cpp:63:3: note: in expansion of macro 'rep'
   rep(j,circle.size()){
   ^~~
circle_selection.cpp:73:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j+1<circle.size();j++){
               ~~~^~~~~~~~~~~~~~
circle_selection.cpp: In function 'node* intersect(node*, Circle*)':
circle_selection.cpp:2:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,n)for(int i=0;i<(n);i++)
                              ^
circle_selection.cpp:141:3: note: in expansion of macro 'rep'
   rep(i,circle.size()){
   ^~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:158:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n;scanf("%d",&n);
        ~~~~~^~~~~~~~~
circle_selection.cpp:161:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x,y,r;scanf("%d%d%d",&x,&y,&r);
             ~~~~~^~~~~~~~~~~~~~~~~~~

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