답안 #935020

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
935020	2024-02-28T11:49:58 Z	mostafa133	Odašiljači (COCI20_odasiljaci)	C++14	70 / 70	103 ms	508 KB

odasiljaci

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
typedef long double ld;
using namespace std;
using namespace __gnu_pbds;
using ordered_set = tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>;
#define all(x) x.begin(), x.end()
#define fast ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
void dfs(ll cur, vector<bool> &vis, vector<pair<ll, ll>> &v, ld md)
{
	if (vis[cur])
	{
		return;
	}
	vis[cur] = 1;
	for (int i = 0; i < vis.size(); i++)
	{
		if (vis[i])
			continue;
		ll x = abs(v[i].first - v[cur].first), y = abs(v[i].second - v[cur].second);
		ll dis = x * x + y * y;
		if (sqrt(dis) > md)
		{
			// cout << md << ' ' << md * md;
			continue;
		}
		dfs(i, vis, v, md);
	}
	// if ((v[cur].second) > md * md)
	{
		// cout << md << ' ' << md * md;
		// return;
	}
}
int main()
{
	fast;
	// freopen("pails.in", "r", stdin);
	// freopen("pails.out", "w", stdout);
	ll n;
	cin >> n;
	vector<pair<ll, ll>> v(n);
	for (int i = 0; i < n; i++)
	{
		cin >> v[i].first >> v[i].second;
	}
	// ll mx = 0;
	vector<pair<ll, ll>> close(n);
	for (int i = 0; i < n; i++)
	{
		ll mn = LLONG_MAX, mnin = 0;
		for (int j = 0; j < n; j++)
		{
			if (j == i)
			{
				continue;
			}
			ll x = abs(v[i].first - v[j].first), y = abs(v[i].second - v[j].second);
			ll dis = x * x + y * y;
			if (dis < mn)
			{
				mn = dis, mnin = j;
			}
		}
		close[i] = {mnin, mn};
	}
	// for (int i = 0; i < n; i++)
	{
		// cout << i << ": " << close[i].first << ' ' << close[i].second << '\n';
	}
	ld l = 0, r = 1e9;
	vector<bool> vis;
	while (l <= r)
	{
		ld md = (l + r) / 2;
		vis = vector<bool>(n, 0);
		dfs(0, vis, v, md);
		// for (int i = 0; i < n; i++)
		{
			// cout << vis[i];
		}
		// if (md < 2)
		{
			// for (int i = 0; i < n; i++)
			{
				// cout << md;
			}
			// cout << '\n';
		}
		// cout << '\n';
		if (find(all(vis), 0) == vis.end())
		{
			// cout << 1;
			r = md - 1e-7;
		}
		else
		{
			l = md + 1e-7;
		}
	}
	// cout << '\n';
	cout << fixed << setprecision(10) << l / 2;
	return 0;
}

Compilation message

odasiljaci.cpp: In function 'void dfs(ll, std::vector<bool>&, std::vector<std::pair<long long int, long long int> >&, ld)':
odasiljaci.cpp:18:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  for (int i = 0; i < vis.size(); i++)
      |                  ~~^~~~~~~~~~~~

Subtask #1

70.0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	14 ms	348 KB	Output is correct
7	Correct	20 ms	344 KB	Output is correct
8	Correct	50 ms	508 KB	Output is correct
9	Correct	97 ms	388 KB	Output is correct
10	Correct	103 ms	348 KB	Output is correct