제출 #1152275

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1152275		YSH2020	Odašiljači (COCI20_odasiljaci)	C++20	42 / 70	1095 ms	6600 KiB

odasiljaci

#include <bits/stdc++.h>
using namespace std;

long double dist(int x1, int y1, int x2, int y2) {
  cout << setprecision(10); long double ans = pow((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2), 0.5);
  return ans;
}

int 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 = 1e15;
  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 << low;
}

• Subtask 1: 42 / 70