#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;
const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int MAXN=2010, LOG=20;
ll n, m, k, w, h, x, y, t, r, s, cnt;
ll X[MAXN], Y[MAXN], R[MAXN];
int par[MAXN];
pair<int, pii> E[MAXN*MAXN/2];
int ans12=-1, ans13=-1, ans14=-1, ans23=-1, ans24=-1, ans34=-1;
int getpar(int x){
if (par[x]==x) return x;
return par[x]=getpar(par[x]);
}
void join(int x, int y){
par[getpar(x)]=getpar(y);
}
inline void upd(int &x, int d){
if (x==-1) x=d+1;
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
cin>>n>>m>>w>>h;
E[cnt++]={floor(w/2.), {n+2, n+4}};
E[cnt++]={floor(h/2.), {n+1, n+3}};
for (int i=1; i<=n; i++){
cin>>X[i]>>Y[i]>>R[i];
E[cnt++]={floor((Y[i]-R[i])/2.), {i, n+1}};
E[cnt++]={floor((w-X[i]+R[i])/2.), {i, n+2}};
E[cnt++]={floor((h-Y[i]+R[i])/2.), {i, n+3}};
E[cnt++]={floor((X[i]-R[i])/2.), {i, n+4}};
}
for (int i=1; i<=n; i++) for (int j=i+1; j<=n; j++){
ll dx=X[i]-X[j], dy=Y[i]-Y[j], d=dx*dx+dy*dy;
E[cnt++]={floor((sqrt(d)-R[i]-R[j])/2.), {i, j}};
}
sort(E, E+cnt);
//reverse(E, E+cnt);
iota(par, par+MAXN, 0);
for (int i=0; i<cnt; i++){
int x=E[i].second.first, y=E[i].second.second, d=E[i].first;
join(x, y);
//if (d<=1) debug2(x, y)
if (getpar(n+1)==getpar(n+2)){
upd(ans12, d);
upd(ans24, d);
upd(ans23, d);
}
if (getpar(n+1)==getpar(n+3)){
upd(ans12, d);
upd(ans13, d);
upd(ans24, d);
upd(ans34, d);
}
if (getpar(n+1)==getpar(n+4)){
upd(ans12, d);
upd(ans13, d);
upd(ans14, d);
}
if (getpar(n+2)==getpar(n+3)){
upd(ans13, d);
upd(ans23, d);
upd(ans34, d);
}
if (getpar(n+2)==getpar(n+4)){
upd(ans13, d);
upd(ans14, d);
upd(ans23, d);
upd(ans24, d);
}
if (getpar(n+3)==getpar(n+4)){
upd(ans14, d);
upd(ans24, d);
upd(ans34, d);
}
}
while (m--){
cin>>r>>s;
if (s==1){
cout<<"1";
if (r<ans12) cout<<"2";
if (r<ans13) cout<<"3";
if (r<ans14) cout<<"4";
}
if (s==2){
if (r<ans12) cout<<"1";
cout<<"2";
if (r<ans23) cout<<"3";
if (r<ans24) cout<<"4";
}
if (s==3){
if (r<ans13) cout<<"1";
if (r<ans23) cout<<"2";
cout<<"3";
if (r<ans24) cout<<"4";
}
if (s==4){
if (r<ans14) cout<<"1";
if (r<ans24) cout<<"2";
if (r<ans34) cout<<"3";
cout<<"4";
}
cout<<"\n";
}
return 0;
}
/*
5 3
16 11
11 8 1
6 10 1
7 3 2
10 4 1
15 5 1
1 1
2 2
2 1
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
347 ms |
24008 KB |
Output is correct |
| 2 |
Incorrect |
354 ms |
23928 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
1144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
347 ms |
24008 KB |
Output is correct |
| 2 |
Incorrect |
354 ms |
23928 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
