Submission #1152290

#TimeUsernameProblemLanguageResultExecution timeMemory
1152290YSH2020Odašiljači (COCI20_odasiljaci)C++20
56 / 70
1092 ms17476 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
long double dist(int x1, int y1, int x2, int y2) {
  long long dist = (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
  cout << setprecision(30); long double ans = pow(dist, 0.5);
  return ans;
}

signed main() {
  int n; cin >> n;
  vector<pair<int, int>> a(n);
  for (int i = 0; i < n; i++) cin >> a[i].first >> a[i].second;
  long double low = 0;
  long double high = 1e9;
  while (high-low > 1e-6) {
    long double mid = (high+low)/2.0;
    int poss = 1;
    vector<vector<int>> edges(n);
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (i != j and dist(a[i].first, a[i].second, a[j].first, a[j].second) <= mid*2.0) {
          edges[i].push_back(j);
          edges[j].push_back(i);
        }
      }
    }
    int visited[n]; for (int i = 0; i < n; i++) visited[i] = 0;
    for (int i = 0; i < 1; i++) {
      if (visited[i] == 1) continue;
      queue <int> x;
      x.push(i);
      while (x.size() > 0) {
        int a = x.front();
        x.pop();
        for (auto j:edges[a]) {
          if (visited[j] == 0) {
            visited[j] = 1;
            x.push(j);
          }
        }
      }
    }
    int count = 0; for (int i = 0; i < n; i++) count += visited[i];
    if (count != n) low = mid;
    else high = mid;
  }
  cout << setprecision(25) << low;
}
#Verdict Execution timeMemoryGrader output
Fetching results...