#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
const int maxn = 3005;
struct tree {
int x, y, r;
} a[maxn];
typedef tree point;
int par[maxn];
double dist(point p, point q) {
int dx = p.x - q.x;
int dy = p.y - q.y;
return sqrt(dx*dx + dy*dy);
}
int root(int x) {
if(par[x] == x) return par[x];
return par[x] = root(par[x]);
}
void join(int x, int y) {
x = root(x);
y = root(y);
if(x != y) {
par[x] = y;
}
return ;
}
int main() {
int n, m, h, w;
cin >> n >> m >> w >> h;
for(int i = 0; i < n; i++) {
cin >> a[i].x >> a[i].y >> a[i].r;
}
vector <pair <double, pair <int, int>>> v;
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
double gap = dist(a[i], a[j]) - a[i].r - a[j].r;
v.emplace_back(gap, make_pair(i, j));
}
v.emplace_back(a[i].y - a[i].r, make_pair(i, n));
v.emplace_back(w - a[i].x - a[i].r, make_pair(i, n + 1));
v.emplace_back(h - a[i].y - a[i].r, make_pair(i, n + 2));
v.emplace_back(a[i].x - a[i].r, make_pair(i, n + 3));
}
sort(v.begin(), v.end());
int l = 0;
vector <pair <int, int>> u;
vector <pair <int, int>> original;
for(int i = 0; i < m; i++) {
int r, e;
cin >> r >> e;
u.emplace_back(r, e - 1);
}
original = u;
sort(u.begin(), u.end());
for(int i = 0; i < n + 4; i++) {
par[i] = i;
}
map <pair <int, int>, string> mp;
auto same = [&] (int i, int j) { return root(i) == root(j); };
function <bool (int, int)> reach = [&] (int i, int j) {
if(i == j) return true;
if(same(n + i, n + (i + 3) % 4)) return false;
if(same(n + j, n + (j + 3) % 4)) return false;
if((i + 1) % 4 == j) {
return !same(n + i, n + (i + 2) % 4);
}
if((j + 1) % 4 == i) {
return !same(n + j, n + (j + 2) % 4);
}
for(auto p : {i, (i + 3) % 4}) {
for(auto q : {j, (j + 3) % 4}) {
if(same(n + p, n + q)) return false;
}
}
return true;
};
for(int i = 0; i < m; i++) {
while(l < v.size() && v[l].first < 2.0 * u[i].first + eps) {
join(v[l].second.first, v[l].second.second);
++l;
}
string res;
for(int j = 0; j < 4; j++) {
if(reach(u[i].second, j)) res += '0' + j + 1;
}
mp[u[i]] = res;
}
for(auto i : original) {
cout << mp[i] << endl;
}
return 0;
}
Compilation message
park.cpp: In function 'int main()':
park.cpp:81:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(l < v.size() && v[l].first < 2.0 * u[i].first + eps) {
~~^~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
327 ms |
33368 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
359 ms |
10088 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
327 ms |
33368 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
