1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86
| #include <bits/stdc++.h>
inline int rd() { int a = 1, b = 0; char c = getchar(); while (!isdigit(c)) a = c == '-' ? 0 : 1, c = getchar(); while (isdigit(c)) b = b * 10 + c - '0', c = getchar(); return a ? b : -b; }
const int N = 1005;
int w, h, n, q, map[N][N], st[11][N][N]; int up[N], f[N], lg[N];
inline void solve(int l, int r, int ql, int qr) { int mid = (l + r) >> 1, pos = 0; for (int i = ql; i <= qr; ++i) if (~up[i]) { int tmp = (mid - i) * (mid - i) + up[i] * up[i]; if (f[mid] > tmp) { f[mid] = tmp; pos = i; } } if (pos && l != mid) solve(l, mid - 1, ql, pos); if (pos && r != mid) solve(mid + 1, r, pos, qr); }
inline int query(int x, int y, int d) { int t = lg[d]; return std::max({ st[t][x][y], st[t][x + d - (1 << t)][y + d - (1 << t)], st[t][x + d - (1 << t)][y], st[t][x][y + d - (1 << t)] }); }
int main() { for (int i = 2; i < N; ++i) lg[i] = lg[i >> 1] + 1; w = rd() + 1, h = rd() + 1, n = rd(); for (int i = 1; i <= n; ++i) { int x = rd() + 1, y = rd() + 1; map[x][y] = 1; } memset(up, -1, sizeof(up)); for (int i = 1; i <= w; ++i) { memset(f, 0x3f, sizeof(f)); for (int j = 1; j <= h; ++j) { if (map[i][j]) up[j] = 0; else if (~up[j]) ++up[j]; } solve(1, h, 1, h); for (int j = 1; j <= h; ++j) st[0][i][j] = f[j]; } memset(up, -1, sizeof(up)); for (int i = w; i >= 1; --i) { memset(f, 0x3f, sizeof(f)); for (int j = 1; j <= h; ++j) { if (map[i][j]) up[j] = 0; else if (~up[j]) ++up[j]; } solve(1, h, 1, h); for (int j = 1; j <= h; ++j) st[0][i][j] = std::min(st[0][i][j], f[j]); } for (int k = 1; k <= 10; ++k) for (int i = 1; i + (1 << k) - 1 <= w; ++i) for (int j = 1; j + (1 << k) - 1 <= h; ++j) st[k][i][j] = std::max({ st[k - 1][i][j], st[k - 1][i][j + (1 << (k - 1))], st[k - 1][i + (1 << (k - 1))][j], st[k - 1][i + (1 << (k - 1))][j + (1 << (k - 1))] }); q = rd(); while (q--) { int x = rd() + 1, y = rd() + 1, d = rd(); if (x - d < 1 x + d > w y - d < 1 y + d > h) { puts("-1"); continue; } int ans = query(x - d, y - d, d * 2 + 1); printf("%.3lf\n", std::sqrt(ans)); } return 0; }
|