#include <bits/stdc++.h>
#include <deque>
using namespace std;
int n, m, w, h;
vector<tuple<int, int, int>> trees;
bool line_of_sight(double x1, double y1, double x2, double y2, int radius) {
for (auto [x, y, base_r] : trees) {
int r = base_r + radius;
double u = (double)((x - x1) * (x2 - x1) + (y - y1) * (y2 - y1)) /
(double)((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
double ex = x1 + clamp(u, 0., 1.) * (x2 - x1);
double ey = y1 + clamp(u, 0., 1.) * (y2 - y1);
double dist = sqrt((ex - x) * (ex - x) + (ey - y) * (ey - y));
if (dist < r)
return false;
}
return true;
}
pair<double, double> get_exit(int exit_id, int radius) {
if (exit_id == 1)
return {radius, radius};
else if (exit_id == 2)
return {w - radius, radius};
else if (exit_id == 3)
return {w - radius, h - radius};
else if (exit_id == 4)
return {radius, h - radius};
else
exit(-1);
}
bool pathfind(int start, int end, int radius) {
auto [startx, starty] = get_exit(start, radius);
auto [endx, endy] = get_exit(end, radius);
deque<tuple<double, double, int>> que;
que.push_back({startx, starty, 0});
while (!que.empty()) {
auto [x, y, r] = que.front();
que.pop_front();
cerr << x << " " << y << " " << que.size() << endl;
if (line_of_sight(x, y, endx, endy, radius))
return true;
for (auto [treex, treey, base_r] : trees) {
int treer = base_r + radius;
double d = sqrt(pow(x - treex, 2) + pow(y - treey, 2));
double alpha = atan2(y - treey, x - treex);
double alpha_inv = atan2(treey - y, treex - x);
vector<tuple<double, double, double, double>> cand = {};
if (d >= r + treer) {
double int_theta = acos((r + treer) / d);
cand.push_back({cos(int_theta + alpha_inv), sin(int_theta + alpha_inv),
cos(int_theta - alpha), sin(int_theta - alpha)});
cand.push_back({cos(int_theta - alpha_inv), sin(int_theta - alpha_inv),
cos(int_theta + alpha), sin(int_theta + alpha)});
double ext_theta = acos(abs(r - treer) / d);
cand.push_back({cos(ext_theta + alpha_inv), sin(ext_theta + alpha_inv),
cos(ext_theta - (M_PI + alpha)),
sin(ext_theta - (M_PI + alpha))});
cand.push_back({cos(ext_theta - alpha_inv), sin(ext_theta - alpha_inv),
cos(ext_theta - (M_PI - alpha)),
sin(ext_theta - (M_PI - alpha))});
}
for (auto [cx, cy, nx, ny] : cand) {
// TODO requires checking if sphere intersects or we are allowed to
// slide
// cx = cx * r + x, cy = cy * r + y;
nx = nx * treer + treex, ny = ny * treer + treey;
if (line_of_sight(x, y, nx, ny, radius))
que.push_back({nx, ny, treer});
}
}
}
return false;
}
int main() {
feenableexcept(FE_DIVBYZERO | FE_INVALID | FE_OVERFLOW);
cin >> n >> m >> w >> h;
for (int i = 0; i < n; i++) {
int x, y, r;
cin >> x >> y >> r;
trees.push_back({x, y, r});
}
vector<pair<int, int>> queries;
for (int i = 0; i < m; i++) {
int r, e;
cin >> r >> e;
queries.push_back({e, r});
}
// Insikt 1: det finns bara 6 möjliga vägar (4 välj 2)
// Insikt 2: vi kan binärsöka över varje vägbredd (ca. log 1e9 \approx 30)
vector<vector<int>> max_width(5, vector<int>(5, -1));
for (int start = 1; start <= 4; start++)
for (int end = start; end <= 4; end++) {
if (start == end) {
max_width[start][end] = 1e9;
max_width[end][start] = 1e9;
continue;
}
int l = 0, r = min(w, h) / 4 + 3;
while (l + 1 < r) {
int mid = (l + r) / 2;
if (pathfind(start, end, mid))
l = mid;
else
r = mid;
}
max_width[start][end] = l;
max_width[end][start] = r;
}
for (auto [e, r] : queries) {
for (int exit = 1; exit <= 4; exit++)
if (r <= max_width[e][exit])
cout << exit;
cout << "\n";
}
return 0;
}
