Submission #1236310

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236310		krab	Odašiljači (COCI20_odasiljaci)	C++20	56 / 70	1094 ms	2376 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();

  stack<int> stack;

  set<int> remaing;

  for (int i = 1; i < n; i++)
    remaing.insert(i);

  stack.push(0);

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

    remaing.erase(node);

    for (int i : remaing) {
      double distance = calculateSquaredDistance(points[node], points[i]);

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

      stack.push(i);
    }
  }

  return remaing.empty();
}

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