#include <bits/stdc++.h>
using namespace std;
#define all(a) (a).begin(), (a).end()
using ld = long double;
using ll = long long;
struct DSU
{
vector<int> papa, sz;
DSU (int N)
{
papa.resize(N + 1);
sz.resize(N + 1);
for(int i = 1; i <= N; i ++)
papa[i] = i, sz[i] = 1;
}
int real_papa(int u)
{
if(papa[u] == u)
return u;
return papa[u] = real_papa(papa[u]);
}
void join(int u, int v)
{
u = real_papa(u);
v = real_papa(v);
if(sz[u] < sz[v])
swap(u, v);
sz[u] += sz[v];
papa[v] = u;
}
bool query(int u, int v)
{
return real_papa(u) == real_papa(v);
}
};
struct debagat
{
int u, v, timp;
};
struct point
{
int x, y, r;
};
struct Query
{
int start, obez, index;
};
bool operator < (debagat a, debagat b)
{
return a.timp < b.timp;
}
bool operator < (Query a, Query b)
{
return a.obez < b.obez;
}
int dist(point a, point b)
{
/*ll rd = sqrtl(1LL * (a.x - b.x) * (a.x - b.x) + 1LL * (a.y - b.y) * (a.y - b.y)), ok = 1;
if(sqrtl(1LL * (a.x - b.x) * (a.x - b.x) + 1LL * (a.y - b.y) * (a.y - b.y)) != (ll)sqrtl(1LL * (a.x - b.x) * (a.x - b.x) + 1LL * (a.y - b.y) * (a.y - b.y)))
ok = 1;
rd -= a.r + b.r;
if(rd < 0)
rd = 0, ok = 0;
if(rd % 2 == 1)
ok = 1;
rd /= 2;
return rd + ok;*/
long double dst = sqrt((long double)((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y))) - a.r - b.r;
dst /= 2.0d;
return (int)dst + 1;
}
bool f[5][5];
string ans[200005];
int main()
{
for(int i = 1; i < 5; i ++)
for(int j = 1; j < 5; j ++)
f[i][j] = true;
int n, m, h, w;
cin >> n >> m >> w >> h;
vector<point> p(n + 1);
DSU ds(n + 4);
for(int i = 1; i <= n; i ++)
cin >> p[i].x >> p[i].y >> p[i].r;
vector<debagat> v;
for(int i = 1; i <= n; i ++)
for(int j = i + 1; j <= n; j ++)
v.push_back({i, j, dist(p[i], p[j])});
for(int i = 1; i <= n; i ++)
v.push_back({i, n + 1, dist(p[i], {0, p[i].y, 0})});
for(int i = 1; i <= n; i ++)
v.push_back({i, n + 2, dist(p[i], {p[i].x, 0, 0})});
for(int i = 1; i <= n; i ++)
v.push_back({i, n + 3, dist(p[i], {w, p[i].y, 0})});
for(int i = 1; i <= n; i ++)
v.push_back({i, n + 4, dist(p[i], {p[i].x, h, 0})});
sort(all(v));
vector<Query> grasi;
for(int i = 1; i <= m; i ++)
{
int l, g;
cin >> g >> l;
grasi.push_back({l, g, i});
}
sort(all(grasi));
int pnt = 0;
for(int i = 0; i < m; i ++)
{
while(pnt < v.size() && v[pnt].timp <= grasi[i].obez)
ds.join(v[pnt].u, v[pnt].v), pnt ++;
if(ds.query(n + 1, n + 2))
for(int j = 1; j < 5; j ++)
if(j != 1)
f[1][j] = f[j][1] = false;
if(ds.query(n + 2, n + 3))
for(int j = 1; j < 5; j ++)
if(j != 2)
f[2][j] = f[j][2] = false;
if(ds.query(n + 3, n + 4))
for(int j = 1; j < 5; j ++)
if(j != 3)
f[3][j] = f[j][3] = false;
if(ds.query(n + 1, n + 4))
for(int j = 1; j < 5; j ++)
if(j != 4)
f[4][j] = f[j][4] = false;
if(ds.query(n + 1, n + 3))
for(int j = 1; j <= 2; j ++)
for(int k = 1; k < 5; k ++)
if(j != k)
f[j][k] = f[k][j] = false;
if(ds.query(n + 2, n + 4))
for(int j = 2; j <= 3; j ++)
for(int k = 1; k < 5; k ++)
if(j != k)
f[j][k] = f[k][j] = false;
for(int j = 1; j < 5; j ++)
if(f[grasi[i].start][j])
ans[grasi[i].index] += j + '0';
}
for(int i = 1; i <= m; i ++)
cout << ans[i] << '\n';
}
/*
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
*/
Compilation message
park.cpp: In function 'int main()':
park.cpp:125:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<debagat>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
125 | while(pnt < v.size() && v[pnt].timp <= grasi[i].obez)
| ~~~~^~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
158 ms |
31420 KB |
Output is correct |
| 2 |
Incorrect |
160 ms |
31620 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
47 ms |
8388 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
158 ms |
31420 KB |
Output is correct |
| 2 |
Incorrect |
160 ms |
31620 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
