#include<bits/stdc++.h>
/*
#pragma GCC optimize("-Ofast")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")*/
#define I inline void
#define S struct
#define vi vector<int>
#define vii vector<pair<int,int>>
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std ;
using ll = long long ;
using ld = long double ;
const int N = 5e6 + 7 , mod = 1e9 + 7 ;
const int inf = N ;
// How interesting!
int n, m;
int w, h ;
vector< pair<double,pii> > all ;
double tx[N],ty[N],tr[N] ;
int fat[N] ;
inline int find(int x){return fat[x] = (x == fat[x] ? x : find(fat[x])) ; }
inline bool same(int x, int y){return find(x) == find(y) ; }
void link(int u , int v){
u = find(u) ;
v = find(v) ;
if(u!=v)fat[u] = v ;
}
string ans[N] ;
int main(){
ios_base::sync_with_stdio(0) ;
cin.tie(0) ;
//freopen("in.in" , "r" , stdin) ;
cin >> n >> m;
cin >> w >> h ;
for(int i = 0 ;i < N ; ++ i)fat[i] = i ;
for(int i = 0 ;i < n; ++ i){
cin >> tx[i] >> ty[i] >> tr[i] ;
for(int j = 0 ;j < i ;++ j){
double d = hypot(tx[i] - tx[j] , ty[i] - ty[j]) - tr[i] - tr[j] ;
all.push_back({d , {i , j} }) ;
}
all.push_back({ty[i] - tr[i] , {i , n + 1}}) ;
all.push_back({tx[i] - tr[i] , {i , n + 2}}) ;
all.push_back({w - tx[i] - tr[i] , {i , n + 3}}) ;
all.push_back({h - ty[i] - tr[i] , {i , n + 4}}) ;
}
for(int i = 1 ;i <= m ;++ i){
double r ;
int e ;
cin >> r >> e ;
all.push_back({r * 2 , { - i , e} }) ;
}
sort(all.begin() , all.end()) ;
for(auto u : all){
if(u.second.first < 0){
// query
int j = -(u.second.first + 1) ;
int ant = u.second.second ;
if(same(n + 1 , n + 4) && same(n + 2 , n + 3) ){
ans[j] += char('0' + ant) ;
continue ;
}
else if(same(n + 1, n + 4) ){
if(ant == 1 || ant == 4){
if(!same(n + 1, n + 2) && !same(n + 2, n + 4)){
ans[j] = "14" ;
}else ans[j] = char('0' + ant) ;
}else{
if(!same(n + 1, n + 3) && ! same(n + 3 , n + 4)){
ans[j] = "23" ;
}else ans[j] = char('0' + ant) ;
}
}else if(same(n + 2 , n + 3)){
if(ant == 1 || ant == 2){
if(!same(n + 1 , n + 2) && !same(n + 1 , n + 3)){
ans[j] = "12" ;
}else ans[j] = char('0' + ant) ;
}else{
if(!same(n + 2 , n + 4) && !same(n + 3, n + 4)){
ans[j] = "34" ;
}else ans[j] = char('0' + ant) ;
}
}else{
ans[j] = "1234" ;
}
}else{
// update
if(u.second.second < n){
// cout<< tx[u.second.first] <<" " << ty[u.second.first] <<" "
//<< tx[u.second.second] <<" " << ty[u.second.second] <<"\n" ;
}
link(u.second.first ,u.second.second) ;
}
}
for(int i = 0 ;i < m; ++ i){
cout<< ans[i] <<"\n" ;
}
return 0 ;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
492 ms |
209600 KB |
Output is correct |
| 2 |
Incorrect |
497 ms |
209600 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
176 ms |
179048 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
492 ms |
209600 KB |
Output is correct |
| 2 |
Incorrect |
497 ms |
209600 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
