Submission #1066850

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066850		sleepntsheep	Park (BOI16_park)	C++17	0 / 100	436 ms	66200 KiB

park

#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 (stderr)

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);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 27
• Subtask 2: 0 / 31
• Subtask 3: 0 / 42