| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1186608 | prism7k | Park (BOI16_park) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
class DisjointSets {
private:
vector<int> parents;
vector<int> sizes;
public:
DisjointSets(int sz) : parents(sz + 1), sizes(sz + 1, 1) {
for(int i = 1; i <= sz; ++i) parents[i] = i;
}
int find(int x) {
return parents[x] == x ? x : (parents[x] = find(parents[x]));
}
void unite(int x, int y) {
int xr = find(x);
int yr = find(y);
if(xr == yr) return;
if(sizes[xr] < sizes[yr]) swap(xr, yr);
parents[yr] = xr;
sizes[xr] += sizes[yr];
}
bool same(int x, int y) {
return find(x) == find(y);
}
};
struct tree {
int x, y, r, id;
};
struct edge {
int u, v;
double w;
bool operator<(const edge &other) {
return w < other.w;
}
};
struct visitor {
int r, e, id;
bool operator<(const visitor &other) {
return r < other.r;
}
};
bool l[100000][4];
vector<tree> trees;
vector<edge> edges;
vector<visitor> visitors;
int main() {
int n, m; cin >> n >> m;
int w, h; cin >> w >> h;
auto get_dist = [&](int x1, int x2, int y1, int y2, int r1, int r2) {
return sqrt(1LL * (x1 - x2) * (x1 - x2) + 1LL * (y1 - y2) * (y1 - y2)) - r1 - r2;
};
for(int i = 0; i < n; ++i) {
int x, y, r;
cin >> x >> y >> r;
trees.push_back({x, y, r, i + 4});
edges.push_back({0, i + 4, get_dist(0, x, y, y, 0, r)});
edges.push_back({1, i + 4, get_dist(x, x, 0, y, 0, r)});
edges.push_back({2, i + 4, get_dist(x3, w, y, y, 0, r)});
edges.push_back({3, i + 4, get_dist(x, x, h, y, 0, r)});
}
for(int i = 0; i < n; ++i) {
tree a = trees[i];
for(int j = i + 1; j < n; ++j) {
tree b = trees[j];
edges.push_back({a.id, b.id, get_dist(a.x, b.x, a.y, b.y, a.r, b.r)});
}
}
for(int i = 0; i < m; ++i) {
int r, e;
cin >> r >> e;
visitors.push_back({r, --e, i});
}
int edge_id = 0;
sort(edges.begin(), edges.end());
sort(visitors.begin(), visitors.end());
DisjointSets dsu(n + 4);
for(auto[vis_r, vis_e, vis_id] : visitors) {
int vis_d = vis_r * 2;
while(edge_id < (int)edges.size() && edges[edge_id].w < vis_d) {
edge cur = edges[edge_id];
dsu.unite(cur.u, cur.v);
edge_id++;
}
bool ltr = dsu.same(0, 2), btt = dsu.same(1, 3);
bool ltb = dsu.same(0, 1), btr = dsu.same(1, 2);
bool rtt = dsu.same(2, 3), ttl = dsu.same(3, 0);
// bottom left
if(
vis_e == 0 ||
(vis_e == 1 && !ltb && !btt) ||
(vis_e == 2 && !ltb && !btt && !ltr) ||
(vis_e == 3 && !ltb && !ltr)
) l[vis_id][0] = true;
// bottom right
if(
vis_e == 1 ||
(vis_e == 0 && !btr && !btt) ||
(vis_e == 2 && !btr && !ltr) ||
(vis_e == 3 && !btr && !btt && !ltr)
) l[vis_id][1] = true;
// top right
if(
vis_e == 2 ||
(vis_e == 0 && !rtt && !btt && !ltr) ||
(vis_e == 1 && !rtt && !ltr) ||
(vis_e == 3 && !rtt && !btt)
) l[vis_id][2] = true;
// top left
if(
vis_e == 3 ||
(vis_e == 0 && !ttl && !ltr) ||
(vis_e == 1 && !ttl && !ltr && !btt) ||
(vis_e == 2 && !ttl && !btt)
) l[vis_id][3] = true;
}
for(int i = 0; i < m; ++i) {
if(l[i][0]) cout << "1";
if(l[i][1]) cout << "2";
if(l[i][2]) cout << "3";
if(l[i][3]) cout << "4";
cout << "\n";
}
}