Submission #77863

#	Time	Username	Problem	Language	Result	Execution time	Memory
77863		autumn_eel	Circle selection (APIO18_circle_selection)	C++14	100 / 100	2346 ms	90580 KiB

circle_selection

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

int ans[400000];
struct Circle{
	double x,y,r;
	int id;
	double bbox[2][2];
	Circle(){}
	Circle(double x,double y,double 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{
	double bbox[2][2];
	node*l,*r;
	vector<Circle*>circle;
};
double area(double bbox[2][2]){
	return (bbox[1][0]-bbox[0][0])*(bbox[1][1]-bbox[0][1]);
}
void init(double bbox[2][2]){
	bbox[0][0]=bbox[0][1]=INF;
	bbox[1][0]=bbox[1][1]=-INF;
}
void mergeAABB(double bbox[2][2],double bbox2[2][2],double 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,double 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.
 
inline void setleaf(vector<Circle*>circle,node*n){
	n->l=n->r=NULL;
	n->circle=circle;
}
struct st{
	double cost;
	int id;
	bool operator<(const st&r)const{
		return cost<r.cost;
	}
};
st calc(vector<Circle*>&circle,double s){
	st res{t_tri*circle.size(),-1};
	double box[2][2];init(box);
	vector<double>s1(circle.size());
	rep(j,circle.size()){
		mergeAABB(box,circle[j]->bbox,box);
		s1[j]=area(box);
	}
	init(box);
	vector<double>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++){
		double cost=2*t_aabb+(s1[j]/s)*(j+1)*t_tri+(s2[j+1]/s)*(circle.size()-j-1)*t_tri;
		if(res.cost>cost){
			res.cost=cost;
			res.id=j;
		}
	}
	return res;
}
void build(vector<Circle*>&circle,node*n,int depth){
	createAABB(circle,n->bbox);
	st ans{INF,-1};
	double s=area(n->bbox);
	if(depth%16==0){
		int axis=-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;
			});
			st res=calc(circle,s);
			if(res<ans){
				ans=res;
				axis=i;
			}
		}
		if(ans.id==-1){
			setleaf(circle,n);
			return;
		}
		sort(circle.begin(),circle.end(),[&](auto a,auto b){
			if(axis==0)return a->x<b->x;
			return a->y<b->y;
		});
	}
	else{
		ans=calc(circle,s);
	}
	if(ans.id==-1){
		setleaf(circle,n);
	}
	else{
		n->l=&bvh[pointer++];
		n->r=&bvh[pointer++];
		vector<Circle*>left(circle.begin(),circle.begin()+ans.id+1);
		vector<Circle*>right(circle.begin()+ans.id+1,circle.end());
		build(left,n->l,depth+1);
		build(right,n->r,depth+1);
	}
}
inline bool intersect(Circle*c1,Circle*c2){
	return pow(c1->x-c2->x,2)+pow(c1->y-c2->y,2)<=pow(c1->r+c2->r,2);
}
inline bool intersect(double bbox1[2][2],double 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;
}
node*intersect(node*n,Circle*c){
	if(!intersect(c->bbox,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;
	}
}

//~ #define DEBUG
Circle c[400000];

int main(){
#ifdef DEBUG
	auto start=chrono::system_clock::now();
#endif
	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,0);
#ifdef DEBUG
	auto end=chrono::system_clock::now();
	double tim=chrono::duration_cast<chrono::milliseconds>(end-start).count();
	printf("build time = %.3lf sec\n",tim/1000);
#endif
	memset(ans,-1,sizeof(ans));
	rep(i,n){
		if(ans[c[i].id]!=-1)continue;
		root=intersect(root,&c[i]);
		if(root==NULL)break;
	}
#ifndef DEBUG
	rep(i,n){
		if(i)printf(" ");
		printf("%d",ans[i]+1);
	}
	puts("");
#endif
#ifdef DEBUG
	auto end2=chrono::system_clock::now();
	double tim2=chrono::duration_cast<chrono::milliseconds>(end2-end).count();
	printf("intersection time = %.3lf sec\n",tim2/1000);
	double tim3=chrono::duration_cast<chrono::milliseconds>(end2-start).count();
	printf("total time = %.3lf sec\n",tim3/1000);
#endif
}

Compilation message (stderr)

circle_selection.cpp: In function 'st calc(std::vector<Circle*>&, double)':
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:62:2: note: in expansion of macro 'rep'
  rep(j,circle.size()){
  ^~~
circle_selection.cpp:72:17: 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:145:3: note: in expansion of macro 'rep'
   rep(i,circle.size()){
   ^~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:167: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:170: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: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 30 / 30
• Subtask 6: 13 / 13