//#pragma GCC optimize ("O3") #include<iostream> #include<vector> #include<set> #include<map> #include<iomanip> #include <cassert> #include<algorithm> #include <cstring> #include<unordered_set> #include<queue> #include <array> #include<cmath> #include<unordered_map> #include<queue> #include <list> #include <bitset> using namespace std; #define int long long #define pii pair<int,int> #define LL long long //#pragma GCC optimize("O3,unroll-loops") //#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt”) int INF = 1e18; int n, m, w, h; vector<pii>events; vector<vector<int>>ans; vector<pair<pii, int>>trees; int rel[1000][1000]; int firstworks[1000][1000]; struct DSU{ vector<int> par; vector<int>sz; DSU(int _n){ par = vector<int>(_n + 1); sz = vector<int>(_n + 1, 1); for(int i = 0; i <= _n; ++i){ par[i] = i; } } //with path compression int get(int x) { return (par[x] == x ? x : (par[x] = get(par[x]))); } //small to large merging void uni(int a, int b) { a = get(a); b = get(b); if(a == b) return; if(sz[a] > sz[b]) { swap(a, b); } sz[b] += sz[a]; par[a] = b; } bool sameset(int a, int b){ return get(a) == get(b); } }; int distsq(pii a, pii b){ return (b.first - a.first) * (b.first - a.first) + (b.second - a.second) * (b.second - a.second); } bool canpass(int rad, int t1, int t2){ int dsq = distsq(trees[t1].first, trees[t2].first); if(rad == 2 && t1 == 3 + 3 && t2 == 5 + 3){ //cout << "AYYO"; //cout << dsq << endl; //cout << (2 * rad + trees[t1].second + trees[t2].second) * (2 * rad + trees[t1].second + trees[t2].second) << endl; } if((2 * rad + trees[t1].second + trees[t2].second) * (2 * rad + trees[t1].second + trees[t2].second) <= dsq){ return true; } return false; } bool check(int rad, int ent, int ex){ //horz = 0, vertical = 1 DSU dsu(n + 10); for(int i = 4; i < n + 4; ++i){ auto [x, y] = trees[i].first; for(int j = 0; j < n + 4; ++j){ if(i == j) continue; if(j >= 4){ if(!canpass(rad, i, j)){ dsu.uni(i, j); //cout << i - 3 << " " << j - 3 << endl; } } else{ int space = 0; if(j == 0){ space = h - y; } if(j == 1){ space = x; } if(j == 2){ space = y; } if(j == 3){ space = w - x; } space -= trees[i].second; if(space < 2 * rad) dsu.uni(i, j); } } } if(ent == 1){ if(dsu.sameset(1, 2)) return false; } if(ent == 2){ if(dsu.sameset(2, 3)) return false; } if(ent == 3){ if(dsu.sameset(0, 3)) return false; } if(ent == 4){ if(dsu.sameset(1, 0)) return false; } int r = rel[ent][ex]; if(r == 0){ // vertical movement if(dsu.sameset(1, 3)) return false; } if(r == 1){ //horizontal moment if(dsu.sameset(0, 2)) return false; } if(r == 2){ if(ex == 3){ if(dsu.sameset(1, 2) || dsu.sameset(0, 3)) return false; } if(ex == 4){ if(dsu.sameset(1, 0) || dsu.sameset(2, 3)) return false; } } // cout << "YO we made it: " << rad << " " << ent << " " << ex << endl; return true; } void solve(int ent){ for(int ex = ent + 1; ex <= 4; ++ex){ int l = 0; int r = 1e9; while(l <= r){ int mid = (l + r) / 2; if(check(mid, ent, ex)){ //ok l = mid + 1; } else{ r = mid - 1; } } int okbound = r; firstworks[ent][ex] = okbound; firstworks[ex][ent] = okbound; // cout << "ex and ent: " << ex << " " << ent << " okbound: " << okbound << endl; } } int32_t main(){ cin.tie(0)->sync_with_stdio(0); cin >> n >> m >> w >> h; events = vector<pii>(m); ans = vector<vector<int>>(m + 1); trees = vector<pair<pii, int>>(4);//4 parts already rel[1][4] = 0; rel[1][2] = 1; rel[1][3] = 2; rel[2][3] = 0; rel[2][4] = 2; rel[3][4] = 1; for(int i = 0; i < n; ++i){ int x, y, r; cin >> x >> y >> r; trees.push_back({{x, y}, r}); } for(int i = 0; i < m; ++i){ int r, e; cin >> r >> e; events[i] = {r, e}; } //solve(2); //return 0; for(int i = 1; i <= 4; ++i){ solve(i); } for(int i = 0; i < m; ++i){ auto [r, e] = events[i]; ans[i].push_back(e); for(int j = 1; j <= 4; ++j){ if(j == e) continue; if(r <= firstworks[e][j]){ //it is ok! ans[i].push_back(j); } } } for(int i = 0; i < m; ++i){ for(int j : ans[i]) cout << j << " "; cout << "\n"; } }