#include <bits/stdc++.h>
using namespace std;
#define int ll
#define double long double
typedef long long ll;
typedef pair<int, int> pii;
#define FastIO cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
#define FileIO freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define F first
#define S second
#define max_heap(T) priority_queue<T>
#define min_heap(T) priority_queue<T, vector<T>, greater<T>>
#define fr(i,a,b) for(int i=a;i<b;i++)
#define frr(i,a,b) for(int i=a;i>b;i--)
#define frin(i,A) for(auto &i : A)
#define frp(a,b,A) for(auto [a, b] : A)
#define SZ(x) (int)x.size()
#define all(A) A.begin(), A.end()
#define mins(a,b) a = min(a,b)
#define maxs(a,b) a = max(a,b)
#define pb push_back
#define kill(x) cout << x << '\n', exit(0)
#define md(a) (a%MOD+MOD)%MOD
const ll INF = 4e18;
const ll MOD = 1e9 + 7;
const int MAXN = 2008;
const int LOG = 30;
double dis(pii p1, pii p2) {
double x = p1.F-p2.F, y = p1.S-p2.S;
return sqrt(x*x + y*y);
}
int w, h, n, m;
struct circle { int x, y, r; } C[MAXN];
struct edge {
int u, v;
double w;
edge() {}
edge(int u_, int v_, double w_) {
u = u_, v = v_, w = w_;
}
bool operator < (const edge &e) const {
return w < e.w;
}
};
vector<edge> E;
struct DSU {
int par[MAXN], sz[MAXN];
void clear() {
fr(i, 0, MAXN)
par[i] = i,
sz[i] = 1;
}
int Find(int v) {
return v == par[v] ? v : par[v] = Find(par[v]);
}
bool Union(int u, int v) {
if((u = Find(u)) == (v = Find(v)))
return 0;
if(sz[u] < sz[v])
swap(u, v);
par[v] = u;
sz[u] += sz[v];
return 1;
}
} dsu;
double fir[5][5];
void solve() {
cin >> n >> m;
cin >> w >> h;
fr(i, 1, n+1) {
cin >> C[i].x >> C[i].y >> C[i].r;
E.pb({i, n+1, (h-(C[i].y+C[i].r))});
E.pb({i, n+2, (w-(C[i].x+C[i].r))});
E.pb({i, n+3, (C[i].y-C[i].r)});
E.pb({i, n+4, (C[i].x-C[i].r)});
}
fr(i, 1, n+1)
fr(j, i+1, n+1)
E.pb({i, j, dis({C[i].x, C[i].y}, {C[j].x, C[j].y})-C[i].r-C[j].r});
sort(all(E));
dsu.clear();
fr(i, 1, 5)
fr(j, 1, 5)
fir[i][j] = INF;
frin(e, E) {
dsu.Union(e.u, e.v);
fr(i, 1, 5)
fr(j, 1, 5)
if(i != j && dsu.Find(n+i) == dsu.Find(n+j))
mins(fir[i][j], e.w);
}
fr(i, 1, 5)
fr(j, 1, 5)
cout << i << ' ' << j << ' ' << fir[i][j] << '\n';
while(m--) {
ll r;
int e;
cin >> r >> e;
r *= 2;
if(e == 1) {
cout << 1;
if(min({fir[1][3], fir[2][3], fir[3][4]}) >= r) cout << 2;
if(min({fir[1][3], fir[2][4], fir[3][4], fir[1][2]}) >= r) cout << 3;
if(min({fir[2][4], fir[1][4], fir[3][4]}) >= r) cout << 4;
}
if(e == 2) {
if(min({fir[1][3], fir[2][3], fir[3][4]}) >= r) cout << 1;
cout << 2;
if(min({fir[2][4], fir[1][2], fir[2][3]}) >= r) cout << 3;
if(min({fir[1][3], fir[2][4], fir[2][3], fir[1][4]}) >= r) cout << 4;
}
if(e == 3) {
if(min({fir[1][3], fir[2][4], fir[3][4], fir[1][2]}) >= r) cout << 1;
if(min({fir[2][4], fir[1][2], fir[2][3]}) >= r) cout << 2;
cout << 3;
if(min({fir[1][2], fir[1][4], fir[1][3]}) >= r) cout << 4;
}
if(e == 4) {
if(min({fir[2][4], fir[1][4], fir[3][4]}) >= r) cout << 1;
if(min({fir[1][3], fir[2][4], fir[2][3], fir[1][4]}) >= r) cout << 2;
if(min({fir[1][2], fir[1][4], fir[1][3]}) >= r) cout << 3;
cout << 4;
}
cout << '\n';
}
}
int32_t main() {
FastIO
int T = 1;
// cin >> T;
while(T--)
solve();
return 0;
}
Compilation message
park.cpp: In function 'void solve()':
park.cpp:78:25: warning: narrowing conversion of '(h - (C[i].circle::y + C[i].circle::r))' from 'll' {aka 'long long int'} to 'long double' [-Wnarrowing]
78 | E.pb({i, n+1, (h-(C[i].y+C[i].r))});
| ~~^~~~~~~~~~~~~~~~~
park.cpp:79:25: warning: narrowing conversion of '(w - (C[i].circle::x + C[i].circle::r))' from 'll' {aka 'long long int'} to 'long double' [-Wnarrowing]
79 | E.pb({i, n+2, (w-(C[i].x+C[i].r))});
| ~~^~~~~~~~~~~~~~~~~
park.cpp:80:30: warning: narrowing conversion of '(C[i].circle::y - C[i].circle::r)' from 'll' {aka 'long long int'} to 'long double' [-Wnarrowing]
80 | E.pb({i, n+3, (C[i].y-C[i].r)});
| ~~~~~~~^~~~~~~~
park.cpp:81:30: warning: narrowing conversion of '(C[i].circle::x - C[i].circle::r)' from 'll' {aka 'long long int'} to 'long double' [-Wnarrowing]
81 | E.pb({i, n+4, (C[i].x-C[i].r)});
| ~~~~~~~^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
503 ms |
67756 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
2512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
503 ms |
67756 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
