| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1066850 |
2024-08-20T08:05:30 Z |
sleepntsheep |
Park (BOI16_park) |
C++17 |
|
436 ms |
66200 KB |
#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; }
ld cut1{1e18}, cut2{1e18}, cut3{1e18}, cut4{1e18}, cutv{1e18}, cuth{1e18};
void check_cut(ld 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(sqrtl(sqre(x[i] - x[j]) + sqre(y[i] - y[j])) - r[i] - r[j], 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;
}
Compilation message
park.cpp: In function 'int main()':
park.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
38 | scanf("%d%d%d%d", &n, &m, &w, &h);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:42:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
42 | for (int i = 0; i < n; ++i) scanf("%d%d%d", x + i, y + i, r + i);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
68 | scanf("%d%d", &rad, &corner);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
436 ms |
66200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
1628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
436 ms |
66200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
