Submission #882747

#	Time	Username	Problem	Language	Result	Execution time	Memory
882747		binh192004	Odašiljači (COCI20_odasiljaci)	C++17	70 / 70	456 ms	9092 KiB

odasiljaci

#include <bits/stdc++.h>

using namespace std;

typedef long double ld;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define int long long
#define double long double
#define all(x) (x).begin(), (x).end()
#define pii pair<int, int>
#define lowbit(x) x & (-x);
#define inf 1e18
#define _inf -1e18
#define pyes cout << "YES" << endl
#define pno cout << "NO" << endl
#define inv(a) for (int& x: a) cin >> x
#define pri(a) for (int& x: a) cout << x << ' '
int const MOD = 998244353;
int const lg = 20;
int const block = 500;
// int block;
int const MAX = 1e3 + 1, N = 20;
int n, m, q, k, p;
void bexuyen67() {
      cin >> n;
      vector<pair<double, double>> a(n);
      for (auto& it: a)
            cin >> it.first >> it.second;
      double l = 0, r = 1e9;
      double res;
      auto dis = [&](pair<double, double> a, pair<double, double> b){
            double x = (a.first - b.first) * (a.first - b.first);
            double y = (a.second - b.second) * (a.second - b.second);
            return sqrt(x + y);
      };
      vector<bool> vs(n);
      auto dfs = [&](auto binh, int u, vector<vector<int>>& g) -> void{
            vs[u] = 1;
            for (int v: g[u]){
                  if (!vs[v])
                        binh(binh, v, g);
            }
      };
      auto can = [&](double mid){
            vector<vector<int>> g(n);
            for (int i = 0; i < n; i++){
                  for (int j = i + 1; j < n; j++){
                        if (dis(a[i], a[j]) <= mid*2.0){
                              g[i].push_back(j);
                              g[j].push_back(i);
                        }
                  }
            }
            fill(all(vs), 0);
            dfs(dfs, 0, g);
            for (int i = 0; i < n; i++)
                  if (!vs[i])
                        return false;
            return true;
      };
//      cout << can(0.7071068);
      for (int t = 0; t < 100; t++){
            double mid = (l + r)/2;
            if (can(mid)){
                  r = mid;
                  res = mid;
            }
            else l = mid;
      }
      cout << res;
}


signed main() {
#ifdef binhball
      freopen("input.txt", "r", stdin);
      freopen("output.txt", "w", stdout);
#endif
      cin.tie(0)->sync_with_stdio(0);
      cout << fixed << setprecision(15);
      int t = 1;
//         cin >> t;
      while (t--)
            bexuyen67();
}

• Subtask 1: 70 / 70