#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
ll x[2023],y[2023],r[2023],p[2023],g[5][5];
struct E {ll a,b,w;}; ll findP(ll a) {return p[a]<0?a:p[a]=findP(p[a]);}
void unite(ll a, ll b){
a=findP(a); b=findP(b); if(a==b) return; if(p[a]>p[b]) swap(a,b); p[a]+=p[b]; p[b]=a;
}
bool f(ll a, ll b, ll r) {return g[a][b]<r;}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
ll n,q,w,h; cin >>n>>q>>w>>h; vector<E> ee;
for(ll i=5;i<=n+4;i++){
cin >>x[i]>>y[i]>>r[i];
ee.pb({1,i,h-y[i]-r[i]}); ee.pb({2,i,w-x[i]-r[i]}); ee.pb({3,i,y[i]-r[i]}); ee.pb({4,i,x[i]-r[i]});
for(ll j=5;j<i;j++) ee.pb({j,i,(ll)(sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]))-r[i]-r[j])});
}sort(ee.begin(),ee.end(),[](E &i, E &j) {return i.w<j.w;});
memset(g,-1,sizeof(g)); memset(p,-1,sizeof(p));
for(auto[a,b,w]:ee){
unite(a,b);
for(ll i=1;i<=4;i++){
for(ll j=i+1;j<=4;j++){
if(g[i][j]==-1 && findP(i)==findP(j)) g[i][j]=g[j][i]=w;
}
}
}while(q--){
ll R,pp; cin >>R>>pp; R*=2; vector<ll> ok(5,1);
if(pp==1){
if(f(3,4,R)) ok[2]=ok[3]=ok[4]=0; if(f(4,1,R)) ok[4]=0; if(f(1,2,R)) ok[3]=0;
if(f(2,3,R)) ok[2]=0; if(f(1,3,R)) ok[2]=ok[3]=0; if(f(2,4,R)) ok[4]=ok[3]=0;
}else if(pp==2){
if(f(3,4,R)) ok[1]=0; if(f(4,1,R)) ok[4]=0; if(f(1,2,R)) ok[3]=0;
if(f(2,3,R)) ok[1]=ok[3]=ok[4]=0; if(f(1,3,R)) ok[1]=ok[4]=0; if(f(2,4,R)) ok[4]=ok[3]=0;
}else if(pp==3){
if(f(3,4,R)) ok[1]=0; if(f(4,1,R)) ok[4]=0; if(f(1,2,R)) ok[1]=ok[2]=ok[4]=0;
if(f(2,3,R)) ok[2]=0; if(f(1,3,R)) ok[1]=ok[4]=0; if(f(2,4,R)) ok[1]=ok[2]=0;
}else{
if(f(3,4,R)) ok[1]=0; if(f(4,1,R)) ok[1]=ok[2]=ok[3]=0; if(f(1,2,R)) ok[3]=0;
if(f(2,3,R)) ok[2]=0; if(f(1,3,R)) ok[2]=ok[3]=0; if(f(2,4,R)) ok[1]=ok[2]=0;
}for(ll i=1;i<=4;i++) if(ok[i]) cout <<i;
cout << "\n";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |