Submission #1152298

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152298		YSH2020	Odašiljači (COCI20_odasiljaci)	C++20	70 / 70	138 ms	16124 KiB

odasiljaci

#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;
}

int p[1005];

int par(int n) {
  if (p[n] == n) return n;
  else return p[n] = par(p[n]);
}

void join(int x, int y) {
  x = par(x);
  y = par(y);
  if (x != y) p[x] = y;
}


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;
  long double dists[n][n];
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) dists[i][j] = dist(a[i].first, a[i].second, a[j].first, a[j].second);
  }
  while (high-low > 1e-6) {
    long double mid = (high+low)/2.0;
    vector<vector<int>> edges(n);
    for (int i = 0; i < n; i++) p[i] = i;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (i != j and dists[i][j] <= mid*2.0) {
          join(i, j);
        }
      }
    }
    int poss = 1;
    for (int i = 0; i < n; i++) {
      if (par(i) != par(0)) poss = 0;
    }
    if (poss) high = mid;
    else low = mid;
  }
  cout << setprecision(25) << low;
}

• Subtask 1: 70 / 70