| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1066859 | sleepntsheep | Park (BOI16_park) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <tuple>
using ll = long long;
using ld = long double;
using namespace std;
template <typename T>
using ve = vector<T>;
int n, m, w, h, x[2002], y[2002], r[2005], ds[2005];
int ds_find(int i) { return ds[i] < 0 ? i : (ds[i] = ds_find(ds[i])); }
int ds_same(int i, int j) { return ds_find(i) == ds_find(j); }
int up() { return n; }
int down() { return n + 1; }
int left() { return n + 2; }
int right() { return n + 3; }
ll sqre(int x) { return x * 1ll * x; }
ll cut1{1e18}, cut2{1e18}, cut3{1e18}, cut4{1e18}, cutv{1e18}, cuth{1e18};
void check_cut(ll w) {
if (cut1 == 1e18 and ds_same(left(), down())) cut1 = w;
if (cut2 == 1e18 and ds_same(down(), right())) cut2 = w;
if (cut3 == 1e18 and ds_same(right(), up())) cut3 = w;
if (cut4 == 1e18 and ds_same(up(), left())) cut4 = w;
if (cuth == 1e18 and ds_same(left(), right())) cuth = w;
if (cutv == 1e18 and ds_same(down(), up())) cutv = w;
}
int main() {
scanf("%d%d%d%d", &n, &m, &w, &h);
for (int i = 0; i < n + 4; ++i) ds[i] = -1;
for (int i = 0; i < n; ++i) scanf("%d%d%d", x + i, y + i, r + i);
ve<tuple<ld, int, int>> el;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
el.emplace_back((long long)(sqrtl(sqre(x[i] - x[j]) + sqre(y[i] - y[j])) - r[i] - r[j] + 1e-7), i, j);
}
el.emplace_back(x[i], left(), i);
el.emplace_back(w - x[i], right(), i);
el.emplace_back(y[i], down(), i);
el.emplace_back(h - y[i], up(), i);
}
sort(el.begin(), el.end());
for (auto [w, u, v] : el) {
if (ds_find(u) == ds_find(v)) continue;
ds[ds_find(u)] = v;
check_cut(w);
}
//printf("%Lf %Lf %Lf %Lf %Lf %Lf\n",cut1,cut2,cut3,cut4,cutv,cuth);
while (m--) {
int corner, rad;
scanf("%d%d", &rad, &corner);
rad *= 2;
switch (corner) {
case 1:
putchar('1');
if (cutv >= rad and cut1 >= rad and cut2 >= rad)
putchar('2');
if (cutv >= rad and cuth >= rad and cut1 >= rad and cut3 >= rad)
putchar('3');
if (cuth >= rad and cut1 >= rad and cut4 >= rad)
putchar('4');
break;
case 2:
if (cutv >= rad and cut1 >= rad and cut2 >= rad)
putchar('1');
putchar('2');
if (cuth >= rad and cut2 >= rad and cut3 >= rad)
putchar('3');
if (cutv >= rad and cuth >= rad and cut4 >= rad and cut2 >= rad)
putchar('4');
break;
case 3:
if (cutv >= rad and cuth >= rad and cut1 >= rad and cut3 >= rad)
putchar('1');
if (cuth >= rad and cut2 >= rad and cut3 >= rad)
putchar('2');
putchar('3');
if (cutv >= rad and cut3 >= rad and cut4 >= rad)
putchar('4');
break;
case 4:
if (cuth >= rad and cut1 >= rad and cut4 >= rad)
putchar('1');
if (cutv >= rad and cuth >= rad and cut4 >= rad and cut2 >= rad)
putchar('2');
if (cutv >= rad and cut3 >= rad and cut4 >= rad)
putchar('3');
putchar('4');
break;
}
putchar('\n');
}
return 0;
}