제출 #1318102

#제출 시각아이디문제언어결과실행 시간메모리
1318102raminqOdašiljači (COCI20_odasiljaci)C++20
70 / 70
93 ms436 KiB
#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<long long> x(n), y(n); for (int i = 0; i < n; i++) { cin >> x[i] >> y[i]; } if (n == 1) { cout << "0.0000000000" << endl; return 0; } double left = 0, right = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { double dx = x[i] - x[j]; double dy = y[i] - y[j]; double dist = sqrt(dx*dx + dy*dy); if (dist > right) right = dist; } } for (int iter = 0; iter < 60; iter++) { double mid = (left + right) / 2; vector<bool> visited(n, false); queue<int> q; q.push(0); visited[0] = true; int count = 1; while (!q.empty()) { int u = q.front(); q.pop(); for (int v = 0; v < n; v++) { if (!visited[v]) { double dx = x[u] - x[v]; double dy = y[u] - y[v]; double dist = sqrt(dx*dx + dy*dy); if (dist <= 2 * mid) { visited[v] = true; q.push(v); count++; } } } } if (count == n) { right = mid; } else { left = mid; } } cout << fixed << setprecision(10) << right << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...