#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |