#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define sz(x) (int)x.size()
#define f first
// #define s second
struct circle{
int x, y, r, id;
};
struct edge{
int from, to;
double l;
};
struct person{
int s, r, id;
};
struct DSU{
vector<int> size, parent;
DSU(int n){
size.resize(n, 1);
parent.resize(n);
for (int i=0; i<n; i++){
parent[i] = i;
}
}
int find(int a){
if (parent[a] == a){
return a;
}
return parent[a] = find(parent[a]);
}
void join(int a, int b){
a = find(a);
b = find(b);
if (a == b){
// Same component
return;
}
if (size[a] < size[b]){
// Point a to b
parent[a] = b;
size[b] += size[a];
}else{
// Point b to a
parent[b] = a;
size[a] += size[b];
}
}
};
const int MAXN = 2000+5, MAXM = 1e5+5, L = 0, D = 1, R = 2, U = 3;
int n, m, w, h;
circle arr[MAXN];
person vis[MAXM];
double dist(int a, int b){
if (a < 4 && b < 4){
return -1;
}
if (a < 4){
if (arr[a].x == -1){
return abs(arr[a].y - arr[b].y) - arr[b].r;
}else{
return abs(arr[a].x - arr[b].x) - arr[b].r;
}
}else if (b < 4){
if (arr[b].x == -1){
return abs(arr[b].x -arr[a].y) - arr[a].r;
}else{
return abs(arr[b].y - arr[a].x) - arr[a].r;
}
}
return sqrt((arr[a].x - arr[b].x)*(arr[a].x - arr[b].x) + (arr[a].y - arr[b].y)*(arr[a].y - arr[b].y)) - arr[a].r - arr[b].r;
}
int main(){
cin.tie(0); ios_base::sync_with_stdio(0);
// freopen("file.in", "r", stdin);
// freopen("file.out", "w", stdout);
cin >> n >> m >> w >> h;
n += 4;
arr[0] = {0, -1, 0, 0};
arr[1] = {-1, 0, 0, 1};
arr[2] = {w, -1, 0, 2};
arr[3] = {-1, h, 0, 3};
for (int i=4; i<n; i++){
int x, y, r;
cin >> x >> y >> r;
arr[i] = {x, y, r, i};
}
vector<edge> edges;
for (int i=0; i<n; i++){
for (int j=i+1; j<n; j++){
if (i < 4 && j < 4){
continue;
}
edges.push_back({i, j, dist(i, j)});
}
}
sort(edges.begin(), edges.end(), [](const edge& a, const edge& b){
return a.l < b.l;
});
// for (int i=0; i<sz(edges); i++){
// cout << edges[i].from << " " << edges[i].to << " " << edges[i].l << "\n";
// }
for (int i=0; i<m; i++){
int x, r;
cin >> r >> x;
vis[i] = {x, r, i};
}
sort(vis, vis+m, [](const person& a, const person& b) {return a.r < b.r;});
// for (int i=0; i<m; i++){
// cout << vis[i].f << " " << vis[i].s << "\n";
// }
int e = 0;
vector<set<int>> output(m);
DSU dsu(n);
for (int i=0; i<m; i++){
while (e < sz(edges) && edges[e].l < 2*vis[i].r){
dsu.join(edges[e].from, edges[e].to);
e++;
}
set<int> ans;
ans.insert(vis[i].s);
if (dsu.find(U) != dsu.find(D)){
if (vis[i].s == 1 && dsu.find(D) != dsu.find(R)){
ans.insert(2);
}else if (vis[i].s == 2 && dsu.find(D) != dsu.find(L)){
ans.insert(1);
}else if (vis[i].s == 3 && dsu.find(U) != dsu.find(R)){
ans.insert(4);
}else if (vis[i].s == 4 && dsu.find(U) != dsu.find(L)){
ans.insert(3);
}
}
if (dsu.find(L) != dsu.find(R)){
if (vis[i].s == 1 && dsu.find(L) != dsu.find(U)){
ans.insert(4);
}else if (vis[i].s == 2 && dsu.find(R) != dsu.find(U)){
ans.insert(3);
}else if (vis[i].s == 3 && dsu.find(D) != dsu.find(R)){
ans.insert(2);
}else if (vis[i].s == 4 && dsu.find(D) != dsu.find(L)){
ans.insert(1);
}
}
if (dsu.find(U) != dsu.find(D) && dsu.find(L) != dsu.find(R)){
if (vis[i].s == 1 && dsu.find(U) != dsu.find(R)){
ans.insert(3);
}else if (vis[i].s == 2 && dsu.find(L) != dsu.find(U)){
ans.insert(4);
}else if (vis[i].s == 3 && dsu.find(D) != dsu.find(L)){
ans.insert(1);
}else if (vis[i].s == 4 && dsu.find(D) != dsu.find(R)){
ans.insert(2);
}
}
output[vis[i].id] = ans;
// cout << "\n";
}
for (int i=0; i<m; i++){
for (int j : output[i]){
cout << j;
}
cout << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
188 ms |
33324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
115 ms |
26788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
188 ms |
33324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
