Submission #1264209

#TimeUsernameProblemLanguageResultExecution timeMemory
1264209rafamiunePark (BOI16_park)C++20
0 / 100
1948 ms840 KiB
#include <bits/stdc++.h> using namespace std; #define fr first #define sc second #define int long long #define all(x) (x).begin(), (x).end() const int maxn = 2e3 + 5; const long long inf = 1e18 + 5; int n, w, h; bool N, S, E, W, ok[5];; vector<int> x(maxn), y(maxn), r(maxn), mark(maxn); void dfs(int v, int radius) { if(mark[v]) return; mark[v] = 1; if ((x[v] - r[v]) <= 2 * radius) W = 1; if ((w - x[v] - r[v]) <= 2 * radius) E = 1; if ((y[v] - r[v]) <= 2 * radius) S = 1; if ((h - y[v] - r[v]) <= 2 * radius) N = 1; for(int i = 1; i <= n; i++) { if(mark[i]) continue; __int128 dx = x[i] - x[v], dy = y[i] - y[v]; __int128 dist2 = dx*dx + dy*dy; __int128 sum = r[v] + r[i] + 2*radius; if(dist2 <= sum*sum) { dfs(i, radius); } } } void solve(int radius, int exit) { for(int i = 1; i <= n; i++) mark[i] = 0; ok[1] = ok[2] = ok[3] = ok[4] = 1; for(int i = 1; i <= n; i++) { if(mark[i]) continue; N = 0; S = 0; W = 0; E = 0; dfs(i, radius); if (exit == 1) { if (W && N) { ok[4] = 0; } if (W && E) { ok[4] = 0; ok[3] = 0; } if (W && S) { ok[4] = 0; ok[3] = 0; ok[2] = 0; } if (S && N) { ok[2] = 0; ok[3] = 0; } if (S && E) { ok[2] = 0; } if (N && E) { ok[3] = 0; } } else if (exit == 2) { if (W && N) { ok[4] = 0; } if (W && E) { ok[4] = 0; ok[3] = 0; } if (W && S) { ok[1] = 0; } if (S && N) { ok[1] = 0; ok[4] = 0; } if (S && E) { ok[1] = 0; ok[3] = 0; ok[4] = 0; } if (N && E) { ok[3] = 0; } } else if (exit == 3) { if (W && N) { ok[4] = 0; } if (W && E) { ok[1] = 0; ok[2] = 0; } if (W && S) { ok[1] = 0; } if (S && N) { ok[4] = 0; ok[1] = 0; } if (S && E) { ok[2] = 0; } if (N && E) { ok[1] = 0; ok[2] = 0; ok[4] = 0; } } else if (exit == 4) { if (W && N) { ok[1] = 0; ok[2] = 0; ok[3] = 0; } if (W && E) { ok[1] = 0; ok[2] = 0; } if (W && S) { ok[1] = 0; } if (S && N) { ok[2] = 0; ok[3] = 0; } if (S && E) { ok[2] = 0; } if (N && E) { ok[3] = 0; } } } } int32_t main() { ios::sync_with_stdio(false); cin.tie(NULL); int m; cin >> n >> m >> w >> h; for(int i = 1; i <= n; i++) { cin >> x[i] >> y[i] >> r[i]; } int max_radius[5][5]; for(int i = 1; i <= 4; i++) { for(int j = 1; j <= 4; j++) { if(i == j) max_radius[i][j] = inf; else { int l = 0; int r = 1e9; solve(l, i); if(!ok[j]) max_radius[i][j] = -1; else { while(r - l > 1) { int mid = (l+r)/2; solve(mid, i); if(ok[j]) l = mid; else r = mid; } max_radius[i][j] = l; } } } } while(m--) { int a, b; cin >> a >> b; for(int i = 1; i <= 4; i++) { if(a <= max_radius[b][i]) { cout << i; } } cout << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...