Submission #328084

#	Time	Username	Problem	Language	Result	Execution time	Memory
328084		model_code	Odašiljači (COCI20_odasiljaci)	C++17	70 / 70	107 ms	492 KiB

odasiljaci

#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 1005;
const double eps = 1e-7;

int n, vis;
pii o[maxn];
bool bio[maxn];

ll dist_sqrd(pii x, pii y) {
	return (ll)(x.first - y.first) * (x.first - y.first) +
	       (ll)(x.second - y.second) * (x.second - y.second);
}

void dfs(int x, double r) {
	vis++;
	bio[x] = 1;
	for (int i = 0; i < n; i++)
		if (i != x && bio[i] == 0 && dist_sqrd(o[x], o[i]) < (ll) 4 * r * r) 
			dfs(i, r);
}

bool ok(double r) {
	memset(bio, 0, sizeof bio);
	vis = 0;	
	dfs(0, r);
	return vis == n;
}
	
int main (void) {	
	ios::sync_with_stdio(false);
	scanf("%d", &n);
	for (int i = 0; i < n; i++) 
		scanf("%d %d", &o[i].first, &o[i].second);
	double lo = 0;
	double hi = 1e9;
	while (hi - lo > eps) {
		double mid = (lo + hi) / 2;
		if (ok(mid))
			hi = mid;
		else
			lo = mid;	
	}
	printf("%.10lf\n", lo+1e-9);
	return 0;
}

Compilation message (stderr)

odasiljaci.cpp: In function 'int main()':
odasiljaci.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   40 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
odasiljaci.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   42 |   scanf("%d %d", &o[i].first, &o[i].second);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 70 / 70