Submission #219946

#TimeUsernameProblemLanguageResultExecution timeMemory
219946nicolaalexandraPark (BOI16_park)C++14
100 / 100
1938 ms2040 KiB
#include <bits/stdc++.h> #define DIM 2010 #define INF 1000000000 using namespace std; struct tree{ int x,y,r; }; tree v[DIM]; vector <int> L[DIM]; deque <int> d; int a[5][5],viz[DIM]; int n,m,i,j,x,y,r,c,w,h; int overlap (int i, int val, int c){ if (c == 1){ if (v[i].x - v[i].r - 2 * val < 0) return 1; } else { if (c == 2){ if (v[i].y - v[i].r - 2 * val < 0) return 1; } else { if (c == 3){ if (v[i].x + v[i].r + 2 * val > w) return 1; } else { if (v[i].y + v[i].r + 2 * val > h) return 1; }}} return 0; } int intersectie (int x, int y, int r, int x2, int y2, int r2){ if (1LL * (r + r2) * (r + r2) > 1LL * (x - x2) * (x - x2) + 1LL * (y - y2) * (y - y2)) return 1; return 0; } int verif (int val, int c1, int c2){ /*for (int i=1;i<=n;i++) L[i].clear(); for (int i=1;i<=n;i++) for (int j=i+1;j<=n;j++){ if (intersectie (v[i].x,v[i].y,v[i].r + val, v[j].x,v[j].y,v[j].r + val)){ L[i].push_back(j); L[j].push_back(i); }} */ /// gasesc punctele de start memset (viz,0,sizeof viz); int ok = 0; for (int i=1;i<=n;i++){ if (viz[i]) continue; if (!overlap(i,val,c1)) /// nu poate fi punct de start continue; d.clear(); d.push_back(i); viz[i] = 1; if (overlap(i,val,c2)){ ok = 1; break; } while (!d.empty()){ int nod = d.front(); d.pop_front(); for (int j=1;j<=n;j++){ if (!intersectie (v[nod].x,v[nod].y,v[nod].r + val, v[j].x,v[j].y,v[j].r + val)) continue; if (!viz[j]){ d.push_back(j); viz[j] = 1; if (overlap(j,val,c2)){ ok = 1; break; }}} if (ok) break; } if (ok) break; } return ok; } int main (){ // ifstream cin ("date.in"); // ofstream cout ("date.out"); cin>>n>>m>>w>>h; for (i=1;i<=n;i++) cin>>v[i].x>>v[i].y>>v[i].r; /// raza minima cu care pot sa maresc cercurile a.i. sa blochez o bucata for (i=1;i<=4;i++) for (j=i+1;j<=4;j++){ int st = 0, dr = INF, sol = 0; while (st <= dr){ int mid = (st+dr)>>1; if (verif (mid,i,j)){ sol = mid; dr = mid-1; } else st = mid+1; } a[i][j] = sol; } for (;m--;){ cin>>r>>c; if (c == 1){ cout<<1; if (!(a[1][2] <= r || a[2][4] <= r || a[2][3] <= r)) cout<<2; if (!(a[1][2] <= r || a[2][4] <= r || a[3][4] <= r || a[1][3] <= r)) cout<<3; if (!(a[1][2] <= r || a[1][3] <= r || a[1][4] <= r)) cout<<4; } else { if (c == 2){ if (!(a[1][2] <= r || a[2][4] <= r || a[2][3] <= r)) cout<<1; cout<<2; if (!(a[2][3] <= r || a[1][3] <= r || a[3][4] <= r)) cout<<3; if (!(a[2][3] <= r || a[1][4] <= r || a[1][3] <= r || a[2][4] <= r)) cout<<4; } else { if (c == 3){ if (!(a[1][2] <= r || a[2][4] <= r || a[3][4] <= r || a[1][3] <= r)) cout<<1; if (!(a[2][3] <= r || a[1][3] <= r || a[3][4] <= r)) cout<<2; cout<<3; if (!(a[3][4] <= r || a[1][4] <= r || a[2][4] <= r)) cout<<4; } else { /// c == 4 if (!(a[1][2] <= r || a[1][3] <= r || a[1][4] <= r)) cout<<1; if (!(a[2][3] <= r || a[1][4] <= r || a[1][3] <= r || a[2][4] <= r)) cout<<2; if (!(a[3][4] <= r || a[1][4] <= r || a[2][4] <= r)) cout<<3; cout<<4; } } } cout<<"\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...