제출 #77724

#제출 시각아이디문제언어결과실행 시간메모리
77724autumn_eel원 고르기 (APIO18_circle_selection)C++14
7 / 100
2680 ms48408 KiB
#include <bits/stdc++.h> #define rep(i,n)for(int i=0;i<(n);i++) #define INF 1e10 #define double float 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. 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); double Min=t_tri*circle.size(); int axis=-1,id=-1; double 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; }); 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(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(double x,double y,double minx,double miny,double maxx,double maxy){ return minx<=x&&x<=maxx&&miny<=y&&y<=maxy; } 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); } bool intersect(Circle*c,double 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(pow(bbox[i][0]-c->x,2)+pow(bbox[j][1]-c->y,2)<=pow(c->r,2))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: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: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);
             ~~~~~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...