Submission #69159

#TimeUsernameProblemLanguageResultExecution timeMemory
69159MANcityPark (BOI16_park)C++14
0 / 100
2566 ms16120 KiB
///GAGO_O #include<iostream> #include<cstdio> #include<fstream> #include<algorithm> #include<cmath> #include<map> #include<queue> #include<set> #include<stack> #include<string> #include<cstring> #include<vector> using namespace std; #define for1(i,n) for(int i=1;i<=(int)n;i++) #define for0(i,n) for(int i=0;i<=(int)n;i++) #define forn(i,n) for(int i=n;i>=1;i--) #define fo(i,x,y) for(int i=x;i<=(int)y;i++) #define fr(i,x,y) for(int i=x;i>=(int)y;i--) #define pb push_back #define mp make_pair #define LL long long const LL Mod=1000*1000*1000+7; int n,m; LL w,h; LL x[2002],y[2002],rad[2002]; int used[2002]; int ka_jan[2002][2002]; LL Rad_Now; ///poxiiiiiiiiiiiii int over_lap(LL x1,LL y1,LL r1,LL x2,LL y2,LL r2) { r1+=Rad_Now; r2+=Rad_Now; LL dist=(LL)(x1-x2)*(x1-x2)+(LL)(y1-y2)*(y1-y2); LL R_sum=(LL)(r1+r2)*(LL)(r1+r2); if(R_sum>dist) return 1; return 0; } int Ver_Now; void dfs(int v) { ka_jan[Ver_Now][v]=1; ka_jan[v][Ver_Now]=1; used[v]=1; for1(i,n) { if(used[i]==0 && over_lap(x[v],y[v],rad[v],x[i],y[i],rad[i])==1) dfs(i); } } vector<int> ux_hat(LL x1,LL y1,LL r1) { r1+=Rad_Now; vector<int> ans; if((x1-r1) < Rad_Now) ans.pb(1); if((y1+r1) > (h-Rad_Now)) ans.pb(2); if((x1+r1) > (w-Rad_Now)) ans.pb(3); if((y1-r1) < Rad_Now) ans.pb(4); return ans; } int karagna[5][5]; void pox(int i,int j) { karagna[i][j]=0; karagna[j][i]=0; } void check(LL nrad) { Rad_Now=nrad; for1(i,n) for1(j,n) ka_jan[i][j]=0; for1(i,n) { for1(j,n) used[j]=0; Ver_Now=i; dfs(i); } int hat_i[5]; int hat_j[5]; for1(i,4) for1(j,4) karagna[i][j]=1; for1(i,n) for1(j,n) { if(i!=j && ka_jan[i][j]==1) { vector<int> fi=ux_hat(x[i],y[i],rad[i]); vector<int> fj=ux_hat(x[j],y[j],rad[j]); for1(z,4) { hat_i[z]=0; hat_j[z]=0; } for0(z,fi.size()-1) hat_i[fi[z]]=1; for0(z,fj.size()-1) hat_j[fj[z]]=1; if((hat_i[1]+hat_j[2])==2) { pox(4,1); pox(4,2); pox(4,3); } if((hat_i[1]+hat_j[3])==2) { pox(4,1); pox(4,2); pox(3,1); pox(3,2); } if((hat_i[1]+hat_j[4])==2) { pox(1,4); pox(1,3); pox(1,2); } if((hat_i[2]+hat_j[3])==2) { pox(1,3); pox(4,3); pox(2,3); } if((hat_i[2]+hat_j[4])==2) { pox(1,2); pox(1,3); pox(4,3); pox(4,2); } if((hat_i[3]+hat_j[4])==2) { pox(1,2); pox(4,2); pox(3,2); } } } } int answer[5][5]; int main() { cin>>n>>m; cin>>w>>h; for1(i,n) cin>>x[i]>>y[i]>>rad[i]; for1(i,4) fo(j,i,4) { if(i!=j) { int l=0; int r=1000000000; while(1) { // cout<<l<<" "<<r<<endl; if(l==r) { answer[i][j]=l; answer[j][i]=l; break; } int m=(l+r+1)/2; check(m); if(karagna[i][j]==1) l=m; else r=(m-1); } } } for1(i,m) { LL R; int Ent; cin>>R>>Ent; for1(j,4) if(answer[Ent][j]>=R || j==Ent) cout<<j; cout<<endl; } return 0; } /* 5 3 16 11 11 8 1 6 10 1 7 3 2 10 4 1 15 5 1 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...