#include<bits/stdc++.h>
#define F first
#define S second
#define make make_pair
#define pb push_back
using namespace std;
const int Max = 1e3 + 10;
int X[Max] , Y[Max] , R[Max];
int S[Max]; pair<int , int> Q[Max];
vector<pair<int , pair<int , int>>> E;
string ans[100010];
int par[Max];
int PAR(int a)
{
if(par[a] == a) return a;
return par[a] = PAR(par[a]);
}
void UNI(int a , int b)
{
//cout << "uni " << a << ' ' << b << '\n';
a = PAR(a);
b = PAR(b);
if(a != b) par[a] = b;
}
int main()
{
ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);
int n , m , w , h; cin >> n >> m >> w >> h;
for(int i = 1 ; i <= n + 4 ; i++) par[i] = i;
for(int i = 1 ; i <= n ; i++)
cin >> X[i] >> Y[i] >> R[i];
for(int i = 1 ; i <= n ; i++)
{
for(int j = i + 1 ; j <= n ; j++)
{
double dx = X[i] - X[j];
double dy = Y[i] - Y[j];
double dst = sqrt(dx * dx + dy * dy) - R[i] - R[j];
int w = dst + 1;
//int w = 0;
E.pb(make(w , make(i , j)));
}
int wl = X[i] - R[i] + 1;
int wr = w - X[i] - R[i] + 1;
int wu = Y[i] - R[i] + 1;
int wd = h - Y[i] - R[i] + 1;
E.pb(make(wl , make(i , n + 1)));
E.pb(make(wu , make(i , n + 2)));
E.pb(make(wr , make(i , n + 3)));
E.pb(make(wd , make(i , n + 4)));
}
for(int i = 1 ; i <= m ; i++)
{
int r; cin >> r >> S[i];
r *= 2;
Q[i] = make(r , i);
}
sort(Q + 1 , Q + m + 1);
sort(E.begin() , E.end());
int j = 1;
for(int i = 0 ; i < E.size() ; i++)
{
while(j <= m && Q[j].F < E[i].F)
{
int i = Q[j].S;
int l = PAR(n + 1);
int u = PAR(n + 2);
int r = PAR(n + 3);
int d = PAR(n + 4);
int s = S[i];
//cout << "ans " << i << " " << s << " , " << l << ',' << r << ',' << u << ',' << d << '\n';
if(s == 1)
{
if(l != d && l != r && l != u) ans[i] += '4';
if(d != l && d != u && d != r) ans[i] += '2';
if(l != r && u != d && u != r && d != l) ans[i] += '3';
ans[i] += '1';
}
else if(s == 2)
{
if(d != l && d != r && d != u) ans[i] += '1';
if(r != l && r != d && r != u) ans[i] += '3';
if(r != d && u != l && u != d && l != r) ans[i] += '4';
ans[i] += '2';
}
else if(s == 3)
{
if(u != l && u != r && u != d) ans[i] += '4';
if(r != l && r != u && r != d) ans[i] += '2';
if(l != r && u != d && u != r && d != l) ans[i] += '1';
ans[i] += '3';
}
else
{
if(u != l && u != r && u != d) ans[i] += '3';
if(l != r && l != u && l != d) ans[i] += '1';
if(r != d && u != l && u != d && l != r) ans[i] += '2';
ans[i] += '4';
}
j++;
}
//cout << E[i].F << ' ';
UNI(E[i].S.F , E[i].S.S);
}
while(j <= m)
{
int i = Q[j].S;
int l = PAR(n + 1);
int u = PAR(n + 2);
int r = PAR(n + 3);
int d = PAR(n + 4);
int s = S[i];
//cout << "ans " << i << " " << s << " , " << l << ',' << r << ',' << u << ',' << d << '\n';
if(s == 1)
{
if(l != d && l != r && l != u) ans[i] += '4';
if(d != l && d != u && d != r) ans[i] += '2';
if(l != r && u != d && u != r && d != l) ans[i] += '3';
ans[i] += '1';
}
else if(s == 2)
{
if(d != l && d != r && d != u) ans[i] += '1';
if(r != l && r != d && r != u) ans[i] += '3';
if(r != d && u != l && u != d && l != r) ans[i] += '4';
ans[i] += '2';
}
else if(s == 3)
{
if(u != l && u != r && u != d) ans[i] += '4';
if(r != l && r != u && r != d) ans[i] += '2';
if(l != r && u != d && u != r && d != l) ans[i] += '1';
ans[i] += '3';
}
else
{
if(u != l && u != r && u != d) ans[i] += '3';
if(l != r && l != u && l != d) ans[i] += '1';
if(r != d && u != l && u != d && l != r) ans[i] += '2';
ans[i] += '4';
}
j++;
}
for(int i = 1 ; i <= m ; i++) sort(ans[i].begin() , ans[i].end()) , cout << ans[i] << '\n';
}
Compilation message
park.cpp: In function 'int main()':
park.cpp:66:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for(int i = 0 ; i < E.size() ; i++)
| ~~^~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
6 ms |
6860 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
7 ms |
7628 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
6 ms |
6860 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
