Submission #1236308

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236308		krab	Odašiljači (COCI20_odasiljaci)	C++20	56 / 70	1095 ms	328 KiB

odasiljaci

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;

const double EPS = 1e-9;

ll calculateSquaredDistance(pii a, pii b) {
  ll deltaX = a.first - b.first, deltaY = a.second - b.second;
  return deltaX * deltaX + deltaY * deltaY;
}

bool checkIsPossible(vector<pii> &points, double radius) {
  int n = points.size();

  vector<bool> visited(n);
  stack<int> stack;

  visited[0] = true;
  stack.push(0);

  while (!stack.empty()) {
    int node = stack.top();
    stack.pop();

    for (int i = 0; i < n; i++) {
      if (visited[i])
        continue;

      double distance = calculateSquaredDistance(points[node], points[i]);

      if (4 * radius * radius < distance)
        continue;

      visited[i] = true;
      stack.push(i);
    }
  }

  return count(visited.begin(), visited.end(), true) == n;
}

void solve() {
  int n;
  cin >> n;

  vector<pii> points(n);

  for (auto &[x, y] : points)
    cin >> x >> y;

  double left = 0, right = 5e9;

  while (right - left > EPS) {
    double mid = left + (right - left) * 0.5;

    if (checkIsPossible(points, mid))
      right = mid;
    else
      left = mid;
  }

  cout << fixed << setprecision(10);
  cout << left << '\n';
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  solve();
}

• Subtask 1: 56 / 70