Advertisement
OIQ

Untitled

OIQ
Feb 10th, 2020
227
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.24 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <set>
  5. #include <cmath>
  6. #include <map>
  7. #include <utility>
  8.  
  9.  
  10. using namespace std;
  11. typedef long long ll;
  12.  
  13. vector <pair<int, int>> a;
  14. vector <long double> dist;
  15. vector <bool> used;
  16.  
  17. int minDist() {
  18.     int u = -1;
  19.     long double d = 1e18;
  20.     for (int i = 0; i < a.size(); i++)
  21.         if (!used[i] && dist[i] < d) {
  22.             d = dist[i];
  23.             u = i;
  24.         }
  25.  
  26.     return u;
  27. }
  28.  
  29. void getDist(int v) {
  30.     int x = a[v].first;
  31.     int y = a[v].second;
  32.  
  33.     for (int i = 0; i < a.size(); i++) {
  34.         if (used[i])
  35.             dist[i] = 0;
  36.         else
  37.             dist[i] = min(dist[i], 1.0L * sqrt((x - a[i].first) * (x - a[i].first) + (y - a[i].second) * (y - a[i].second)));
  38.     }
  39. }
  40.  
  41. int main() {
  42.  
  43.     ios_base::sync_with_stdio(false);
  44.     cin.tie(0);
  45.     cout.tie(0);
  46.     cout.precision(2);
  47.     cout << fixed;
  48.  
  49.     int n;
  50.     cin >> n;
  51.    
  52.     a.resize(n);
  53.     dist.resize(n, 1e12);
  54.     used.resize(n, false);
  55.     for (int i = 0; i < n; i++) {
  56.         int x, y;
  57.         cin >> x >> y;
  58.         a[i] = { x, y };
  59.     }
  60.  
  61.     int v = 0;
  62.     long double ans = 0.0;
  63.     dist[v] = 0.0;
  64.     used[v] = true;
  65.     getDist(v);
  66.  
  67.     for (int i = 0; i < n - 1; i++) {
  68.         int u = minDist();
  69.         ans = max(ans, dist[u]);
  70.         used[u] = true;
  71.         v = u;
  72.         getDist(v);
  73.     }
  74.  
  75.     cout << ans;
  76.     return 0;
  77.    
  78. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement