oj.uz

답안 #882747

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
882747 2023-12-03T15:40:05 Z binh192004 Odašiljači (COCI20_odasiljaci) C++17
70 / 70
 456 ms 9092 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long double ld;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define int long long
#define double long double
#define all(x) (x).begin(), (x).end()
#define pii pair<int, int>
#define lowbit(x) x & (-x);
#define inf 1e18
#define _inf -1e18
#define pyes cout << "YES" << endl
#define pno cout << "NO" << endl
#define inv(a) for (int& x: a) cin >> x
#define pri(a) for (int& x: a) cout << x << ' '
int const MOD = 998244353;
int const lg = 20;
int const block = 500;
// int block;
int const MAX = 1e3 + 1, N = 20;
int n, m, q, k, p;
void bexuyen67() {
      cin >> n;
      vector<pair<double, double>> a(n);
      for (auto& it: a)
            cin >> it.first >> it.second;
      double l = 0, r = 1e9;
      double res;
      auto dis = [&](pair<double, double> a, pair<double, double> b){
            double x = (a.first - b.first) * (a.first - b.first);
            double y = (a.second - b.second) * (a.second - b.second);
            return sqrt(x + y);
      };
      vector<bool> vs(n);
      auto dfs = [&](auto binh, int u, vector<vector<int>>& g) -> void{
            vs[u] = 1;
            for (int v: g[u]){
                  if (!vs[v])
                        binh(binh, v, g);
            }
      };
      auto can = [&](double mid){
            vector<vector<int>> g(n);
            for (int i = 0; i < n; i++){
                  for (int j = i + 1; j < n; j++){
                        if (dis(a[i], a[j]) <= mid*2.0){
                              g[i].push_back(j);
                              g[j].push_back(i);
                        }
                  }
            }
            fill(all(vs), 0);
            dfs(dfs, 0, g);
            for (int i = 0; i < n; i++)
                  if (!vs[i])
                        return false;
            return true;
      };
//      cout << can(0.7071068);
      for (int t = 0; t < 100; t++){
            double mid = (l + r)/2;
            if (can(mid)){
                  r = mid;
                  res = mid;
            }
            else l = mid;
      }
      cout << res;
}


signed main() {
#ifdef binhball
      freopen("input.txt", "r", stdin);
      freopen("output.txt", "w", stdout);
#endif
      cin.tie(0)->sync_with_stdio(0);
      cout << fixed << setprecision(15);
      int t = 1;
//         cin >> t;
      while (t--)
            bexuyen67();
}

Subtask #1
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 3 ms 516 KB Output is correct
4 Correct 5 ms 348 KB Output is correct
5 Correct 6 ms 600 KB Output is correct
6 Correct 135 ms 2624 KB Output is correct
7 Correct 136 ms 2624 KB Output is correct
8 Correct 318 ms 6720 KB Output is correct
9 Correct 456 ms 9092 KB Output is correct
10 Correct 422 ms 9048 KB Output is correct