oj.uz

Submission #328084

# Submission time Handle Problem Language Result Execution time Memory
328084 2020-11-15T10:59:11 Z model_code Odašiljači (COCI20_odasiljaci) C++17
70 / 70
 107 ms 492 KB 
#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

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.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 15 ms 364 KB Output is correct
7 Correct 21 ms 364 KB Output is correct
8 Correct 52 ms 364 KB Output is correct
9 Correct 99 ms 364 KB Output is correct
10 Correct 107 ms 492 KB Output is correct