#include<bits/stdc++.h>
using namespace std;
using ll = long long ;
using pll = pair < ll, ll >;
bool B[5][2002] = {false};
bool D[5][5] = {false};
int ataman[2002];
ll Get(ll x) {
if ( x == ataman[x]) return x;
return ataman[x] = Get(ataman[x]);
}
void Unite(int x, int y) {
x = Get(x);
y = Get(y);
if ( x == y) return ;
ataman[x] = y;
for ( int i = 1; i <= 4; i ++) B[i][y] |= B[i][x];
for (int j = 1; j <= 4; j ++) {
for (int i1 = j + 1; i1 <= 4; i1 ++) {
if ( B[j][y] && B[i1][y]) D[j][i1] = 1;
}
}
return ;
}
ll x[2002], y[2002], r[2002];
priority_queue < pll , vector <pll> , greater<pll> > Durvuntal[5];
int main() {
ll n, m, i, j, N, M, x1, Y, y1, R, ind, i1, ans;
cin >> n >> m;
cin >> N >> M;
for (i = 1; i <= n; i ++) ataman[i] = i;
for (i = 1; i <= n; i ++) {
cin >> x[i] >> y[i] >> r[i];
}
vector < pair < double, pair < ll, ll> > > v;
for (i = 1; i <= n; i ++) {
Durvuntal[1].push({y[i] - r[i], i});
Durvuntal[2].push({N - (x[i] + r[i]), i});
Durvuntal[3].push({M - (y[i] + r[i]), i});
Durvuntal[4].push({x[i] - r[i], i});
for (j = i+ 1; j <= n; j ++) {
double S = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
S = sqrt(S);
S = S - r[i] - r[j];
v.push_back({S, {i, j}});
}
}
sort(v.begin(), v.end());
vector < pair < ll, pair < ll, ll > > > Q;
for (i = 1; i <= m; i ++) {
cin >> x1 >> y1;
Q.push_back({x1, {y1, i}});
}
sort(Q.begin(), Q.end());
string Ans[5];
ind= 0;
for (pair < ll, pair < ll, ll > >& P : Q) {
double S = P.first * 2.0;
for (i = 1; i <= 4; i ++) {
while(!Durvuntal[i].empty()) {
pll Pa = Durvuntal[i].top();
if (Pa.first < S) {
Durvuntal[i].pop();
R = Get(Pa.first);
B[i][R] = 1;
for (j = 1; j <= 4; j ++) {
for (i1 = j + 1; i1 <= 4; i1 ++) {
if ( B[j][R] && B[i1][R]) D[j][i1] = 1;
}
}
}
else break;
}
}
while ( ind < v.size() && v[ind].first < S) {
Unite(v[ind].second.first, v[ind].second.second);
ind ++;
}
Y = P.second.first;
if ( Y == 1) {
ans = 1;
if ( !D[1][4] && !D[1][2] && !D[1][3]) ans = ans * 10 + 2;
if ( !D[1][4] && !D[2][3] && !D[1][3] && !D[2][4]) ans = ans * 10 + 3;
if ( !D[1][4] && !D[3][4] && !D[2][4]) ans = ans * 10 + 4;
}
if ( Y == 2) {
ans = 2;
if ( !D[1][4] && !D[1][2] && !D[1][3]) ans = ans * 10 + 1;
if ( !D[1][2] && !D[2][3] && !D[2][4]) ans = ans * 10 + 3;
if ( !D[1][2] && !D[3][4] && !D[2][4] && !D[1][3]) ans = ans * 10 + 4;
}
if ( Y == 3) {
ans = 3;
if ( !D[1][4] && !D[2][3] && !D[1][3] && !D[2][4]) ans = ans * 10 + 1;
if ( !D[1][2] && !D[2][3] && !D[2][4]) ans = ans * 10 + 2;
if ( !D[2][3] && !D[3][4] && !D[1][3]) ans = ans * 10 + 4;
}
if ( Y == 4) {
ans = 1;
if ( !D[1][4] && !D[3][4] && !D[2][4]) ans = ans * 10 + 1;
if ( !D[1][2] && !D[3][4] && !D[2][4] && !D[1][3]) ans = ans * 10 + 2;
if ( !D[2][3] && !D[3][4] && !D[1][3]) ans = ans * 10 + 3;
}
string str = to_string(ans);
sort(str.begin(), str.end());
Ans[P.second.second] = str;
}
for (i = 1; i <= m; i ++) {
cout << Ans[i] << endl;
}
}
Compilation message
park.cpp: In function 'int main()':
park.cpp:81:15: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<double, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | while ( ind < v.size() && v[ind].first < S) {
| ~~~~^~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
280 ms |
97372 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
50 ms |
7492 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
280 ms |
97372 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
