oj.uz

Submission #77718

# Submission time Handle Problem Language Result Execution time Memory
77718 2018-09-30T04:13:00 Z autumn_eel Circle selection (APIO18_circle_selection) C++14
50 / 100
 2994 ms 54696 KB 
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
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]=INT_MAX;
	bbox[1][0]=bbox[1][1]=-INT_MAX;
}
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])*(ll)(j+1)+(s2[j+1])*(ll)(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);
}
bool intersect(int x,int y,int minx,int miny,int maxx,int maxy){
	return minx<=x&&x<=maxx&&miny<=y&&y<=maxy;
}
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);
}
bool intersect(Circle*c,int bbox[2][2]){
	if(intersect(c->x,c->y,bbox[0][0]-c->r,bbox[0][1],bbox[1][0]+c->r,bbox[1][1]))return true;
	if(intersect(c->x,c->y,bbox[0][0],bbox[0][1]-c->r,bbox[1][0],bbox[1][1]+c->r))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("");
}

Compilation message

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:62:3: note: in expansion of macro 'rep'
   rep(j,circle.size()){
   ^~~
circle_selection.cpp:72: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:135:3: note: in expansion of macro 'rep'
   rep(i,circle.size()){
   ^~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:152: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:155: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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23800 KB Output is correct
2 Correct 22 ms 23936 KB Output is correct
3 Correct 21 ms 24016 KB Output is correct
4 Correct 27 ms 24016 KB Output is correct
5 Correct 21 ms 24016 KB Output is correct
6 Incorrect 22 ms 24020 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1708 ms 52320 KB Output is correct
2 Correct 1492 ms 52320 KB Output is correct
3 Correct 1640 ms 52320 KB Output is correct
4 Correct 1655 ms 52320 KB Output is correct
5 Correct 1222 ms 52320 KB Output is correct
6 Correct 1418 ms 52320 KB Output is correct
7 Correct 1222 ms 52320 KB Output is correct
8 Correct 1265 ms 52320 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 52320 KB Output is correct
2 Correct 713 ms 52320 KB Output is correct
3 Correct 2994 ms 54696 KB Output is correct
4 Correct 2802 ms 54696 KB Output is correct
5 Correct 2523 ms 54696 KB Output is correct
6 Correct 1006 ms 54696 KB Output is correct
7 Correct 542 ms 54696 KB Output is correct
8 Correct 101 ms 54696 KB Output is correct
9 Correct 2576 ms 54696 KB Output is correct
10 Correct 2456 ms 54696 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2569 ms 54696 KB Output is correct
2 Correct 2511 ms 54696 KB Output is correct
3 Correct 2141 ms 54696 KB Output is correct
4 Correct 2614 ms 54696 KB Output is correct
5 Correct 2544 ms 54696 KB Output is correct
6 Correct 2099 ms 54696 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23800 KB Output is correct
2 Correct 22 ms 23936 KB Output is correct
3 Correct 21 ms 24016 KB Output is correct
4 Correct 27 ms 24016 KB Output is correct
5 Correct 21 ms 24016 KB Output is correct
6 Incorrect 22 ms 24020 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23800 KB Output is correct
2 Correct 22 ms 23936 KB Output is correct
3 Correct 21 ms 24016 KB Output is correct
4 Correct 27 ms 24016 KB Output is correct
5 Correct 21 ms 24016 KB Output is correct
6 Incorrect 22 ms 24020 KB Output isn't correct
7 Halted 0 ms 0 KB -