oj.uz

Submission #77740

# Submission time Handle Problem Language Result Execution time Memory
77740 2018-09-30T06:53:36 Z autumn_eel Circle selection (APIO18_circle_selection) C++14
7 / 100
 2624 ms 48320 KB 
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define INF 1e10
#define EPS (1e-10)
using namespace std;

int ans[400000];
struct Circle{
	float x,y,r;
	int id;
	float bbox[2][2];
	Circle(){}
	Circle(float x,float y,float 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{
	float bbox[2][2];
	node*l,*r;
	vector<Circle*>circle;
};
float area(float bbox[2][2]){
	return (bbox[1][0]-bbox[0][0])*(bbox[1][1]-bbox[0][1]);
}
void init(float bbox[2][2]){
	bbox[0][0]=bbox[0][1]=INF;
	bbox[1][0]=bbox[1][1]=-INF;
}
void mergeAABB(float bbox[2][2],float bbox2[2][2],float 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,float 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);
	float Min=t_tri*circle.size();
	int axis=-1,id=-1;
	float s=area(n->bbox);
	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;
		});
		float box[2][2];init(box);
		vector<float>s1(circle.size());
		rep(j,circle.size()){
			mergeAABB(box,circle[j]->bbox,box);
			s1[j]=area(box);
		}
		init(box);
		vector<float>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++){
			float cost=2*t_aabb+(s1[j]/s)*(j+1)*t_tri+(s2[j+1]/s)*(circle.size()-j-1)*t_tri;
			if(Min>cost){
				Min=cost;
				axis=i;id=j;
			}
		}
	}
	if(axis==-1){
		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(Circle*c1,Circle*c2){
	return pow(c1->x-(double)c2->x,2)+pow(c1->y-(double)c2->y,2)<=pow(c1->r+(double)c2->r,2);
}
inline bool intersect(float bbox1[2][2],float bbox2[2][2]){
	if(bbox1[1][0]+EPS<bbox2[0][0]||bbox2[1][0]+EPS<bbox1[0][0]||bbox1[1][1]+EPS<bbox2[0][1]||bbox2[1][1]+EPS<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;
	}
}

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/512.,y/512.,r/512.,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:64:3: note: in expansion of macro 'rep'
   rep(j,circle.size()){
   ^~~
circle_selection.cpp:74: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:128:3: note: in expansion of macro 'rep'
   rep(i,circle.size()){
   ^~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:145: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:148: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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB Output is correct
2 Correct 22 ms 23800 KB Output is correct
3 Correct 23 ms 23924 KB Output is correct
4 Correct 22 ms 23924 KB Output is correct
5 Correct 23 ms 23924 KB Output is correct
6 Correct 22 ms 23924 KB Output is correct
7 Correct 22 ms 23924 KB Output is correct
8 Correct 22 ms 23924 KB Output is correct
9 Correct 22 ms 23924 KB Output is correct
10 Correct 25 ms 23924 KB Output is correct
11 Correct 23 ms 24036 KB Output is correct
12 Correct 29 ms 24036 KB Output is correct
13 Correct 23 ms 24036 KB Output is correct
14 Correct 22 ms 24036 KB Output is correct
15 Correct 25 ms 24112 KB Output is correct
16 Correct 24 ms 24112 KB Output is correct
17 Correct 24 ms 24112 KB Output is correct
18 Correct 25 ms 24112 KB Output is correct
19 Correct 36 ms 24388 KB Output is correct
20 Correct 35 ms 24428 KB Output is correct
21 Correct 37 ms 24444 KB Output is correct
22 Correct 41 ms 24444 KB Output is correct
23 Correct 40 ms 24460 KB Output is correct
24 Correct 41 ms 24476 KB Output is correct
25 Correct 41 ms 24476 KB Output is correct
26 Correct 41 ms 24492 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1604 ms 45740 KB Output is correct
2 Correct 1515 ms 45740 KB Output is correct
3 Correct 1460 ms 45740 KB Output is correct
4 Correct 1483 ms 45740 KB Output is correct
5 Incorrect 1260 ms 45740 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 45740 KB Output is correct
2 Correct 671 ms 45740 KB Output is correct
3 Correct 2567 ms 48296 KB Output is correct
4 Correct 2624 ms 48320 KB Output is correct
5 Incorrect 2421 ms 48320 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2513 ms 48320 KB Output is correct
2 Correct 2567 ms 48320 KB Output is correct
3 Correct 2171 ms 48320 KB Output is correct
4 Correct 2455 ms 48320 KB Output is correct
5 Correct 2530 ms 48320 KB Output is correct
6 Incorrect 1965 ms 48320 KB Output isn't correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB Output is correct
2 Correct 22 ms 23800 KB Output is correct
3 Correct 23 ms 23924 KB Output is correct
4 Correct 22 ms 23924 KB Output is correct
5 Correct 23 ms 23924 KB Output is correct
6 Correct 22 ms 23924 KB Output is correct
7 Correct 22 ms 23924 KB Output is correct
8 Correct 22 ms 23924 KB Output is correct
9 Correct 22 ms 23924 KB Output is correct
10 Correct 25 ms 23924 KB Output is correct
11 Correct 23 ms 24036 KB Output is correct
12 Correct 29 ms 24036 KB Output is correct
13 Correct 23 ms 24036 KB Output is correct
14 Correct 22 ms 24036 KB Output is correct
15 Correct 25 ms 24112 KB Output is correct
16 Correct 24 ms 24112 KB Output is correct
17 Correct 24 ms 24112 KB Output is correct
18 Correct 25 ms 24112 KB Output is correct
19 Correct 36 ms 24388 KB Output is correct
20 Correct 35 ms 24428 KB Output is correct
21 Correct 37 ms 24444 KB Output is correct
22 Correct 41 ms 24444 KB Output is correct
23 Correct 40 ms 24460 KB Output is correct
24 Correct 41 ms 24476 KB Output is correct
25 Correct 41 ms 24476 KB Output is correct
26 Correct 41 ms 24492 KB Output is correct
27 Correct 55 ms 48320 KB Output is correct
28 Correct 54 ms 48320 KB Output is correct
29 Correct 54 ms 48320 KB Output is correct
30 Correct 74 ms 48320 KB Output is correct
31 Correct 64 ms 48320 KB Output is correct
32 Correct 64 ms 48320 KB Output is correct
33 Correct 527 ms 48320 KB Output is correct
34 Correct 536 ms 48320 KB Output is correct
35 Correct 494 ms 48320 KB Output is correct
36 Correct 658 ms 48320 KB Output is correct
37 Correct 641 ms 48320 KB Output is correct
38 Correct 624 ms 48320 KB Output is correct
39 Correct 830 ms 48320 KB Output is correct
40 Correct 843 ms 48320 KB Output is correct
41 Correct 683 ms 48320 KB Output is correct
42 Correct 493 ms 48320 KB Output is correct
43 Incorrect 431 ms 48320 KB Output isn't correct
44 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB Output is correct
2 Correct 22 ms 23800 KB Output is correct
3 Correct 23 ms 23924 KB Output is correct
4 Correct 22 ms 23924 KB Output is correct
5 Correct 23 ms 23924 KB Output is correct
6 Correct 22 ms 23924 KB Output is correct
7 Correct 22 ms 23924 KB Output is correct
8 Correct 22 ms 23924 KB Output is correct
9 Correct 22 ms 23924 KB Output is correct
10 Correct 25 ms 23924 KB Output is correct
11 Correct 23 ms 24036 KB Output is correct
12 Correct 29 ms 24036 KB Output is correct
13 Correct 23 ms 24036 KB Output is correct
14 Correct 22 ms 24036 KB Output is correct
15 Correct 25 ms 24112 KB Output is correct
16 Correct 24 ms 24112 KB Output is correct
17 Correct 24 ms 24112 KB Output is correct
18 Correct 25 ms 24112 KB Output is correct
19 Correct 36 ms 24388 KB Output is correct
20 Correct 35 ms 24428 KB Output is correct
21 Correct 37 ms 24444 KB Output is correct
22 Correct 41 ms 24444 KB Output is correct
23 Correct 40 ms 24460 KB Output is correct
24 Correct 41 ms 24476 KB Output is correct
25 Correct 41 ms 24476 KB Output is correct
26 Correct 41 ms 24492 KB Output is correct
27 Correct 1604 ms 45740 KB Output is correct
28 Correct 1515 ms 45740 KB Output is correct
29 Correct 1460 ms 45740 KB Output is correct
30 Correct 1483 ms 45740 KB Output is correct
31 Incorrect 1260 ms 45740 KB Output isn't correct
32 Halted 0 ms 0 KB -