Advertisement
Guest User

Untitled

a guest
May 26th, 2019
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.48 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <map>
  6. #include <stack>
  7. #include <cmath>
  8. #include <set>
  9. #include <utility>
  10. #include <iomanip>
  11. #include <cstdlib>
  12. #include <ctime>
  13. #include <numeric>
  14. #include <unordered_map>
  15.  
  16. using namespace std;
  17.  
  18.  
  19. long long dd(vector<pair<long long, long long> > & dop) {
  20.     int c = dop.size();
  21.     long long ans = 4000000000000000001;
  22.     long long int dist = 0;
  23.     for (int i = 0; i < c; ++i) {
  24.         for (int j = i + 1; j < c; ++j) {
  25.             long long de = (dop[i].first - dop[j].first) * (dop[i].first - dop[j].first) +
  26.                            (dop[i].second - dop[j].second) * (dop[i].second - dop[j].second);
  27.             if (de >= ans)
  28.                 continue;
  29.             for (int k = j + 1; k < c; ++k) {
  30.                 dist = de;
  31.                 dist = max(dist, (dop[i].first - dop[k].first) * (dop[i].first - dop[k].first) +
  32.                                  (dop[i].second - dop[k].second) * (dop[i].second - dop[k].second));
  33.                 dist = max(dist, (dop[j].first - dop[k].first) * (dop[j].first - dop[k].first) +
  34.                                  (dop[j].second - dop[k].second) * (dop[j].second - dop[k].second));
  35.                 ans = min(ans, dist);
  36.             }
  37.         }
  38.     }
  39.     return ans;
  40. }
  41. bool cmp(pair<long long, long long> p1, pair<long long, long long> p2) {
  42.     return (p1.second < p2.second);
  43. }
  44. int main() {
  45.     freopen("input.txt", "r", stdin);
  46.  
  47.  
  48.     int n;
  49.     cin >> n;
  50.     vector<pair<long long, long long> > points(n);
  51.     for (int i = 0; i < n; ++i) {
  52.         cin >> points[i].first >> points[i].second;
  53.     }
  54.  
  55.     random_shuffle(points.begin(), points.end());
  56.     vector<int> used(n);
  57.     int c = 500;
  58.     c = min(c, n);
  59.     vector<pair<long long, long long> > dop;
  60.     if (c < 250) {
  61.         for (int i = 0; i < c; ++i) {
  62.             dop.push_back(points[i]);
  63.         }
  64.     } else
  65.         for (int i = 0; i < c; ++i) {
  66.             int e = rand() % n;
  67.             if (used[e] == 0) {
  68.                 dop.push_back(points[e]);
  69.                 used[e] = 1;
  70.             }
  71.         }
  72.     c = dop.size();
  73.     long long int ans = 4000000000000000001;
  74.  
  75.     long long int dist = 0;
  76.     for (int i = 0; i < c; ++i) {
  77.         for (int j = i + 1; j < c; ++j) {
  78.             long long de = (dop[i].first - dop[j].first) * (dop[i].first - dop[j].first) +
  79.                            (dop[i].second - dop[j].second) * (dop[i].second - dop[j].second);
  80.             if (de >= ans)
  81.                 continue;
  82.             for (int k = j + 1; k < c; ++k) {
  83.                 dist = de;
  84.                 dist = max(dist, (dop[i].first - dop[k].first) * (dop[i].first - dop[k].first) +
  85.                                  (dop[i].second - dop[k].second) * (dop[i].second - dop[k].second));
  86.                 dist = max(dist, (dop[j].first - dop[k].first) * (dop[j].first - dop[k].first) +
  87.                                  (dop[j].second - dop[k].second) * (dop[j].second - dop[k].second));
  88.                 ans = min(ans, dist);
  89.             }
  90.         }
  91.     }
  92.     sort(points.begin(), points.end());
  93.     long long sq = static_cast<long long>(ceil(sqrt(ans)));
  94.     sq*=2;
  95.     vector<vector<pair<long long, long long> > > mm(n);
  96.     vector<vector<pair<long long, long long> > > vec(n);
  97.     mm[0].push_back(points[0]);
  98.     int last = 0;
  99.     for (int i = 1; i < n; ++i) {
  100.         if (points[i].first/sq == mm[last][0].first/sq)
  101.             mm[last].push_back(points[i]);
  102.         else {
  103.             ++last;
  104.             mm[last].push_back(points[i]);
  105.         }
  106.     }
  107.     mm.resize(last+1);
  108.     sort(mm[0].begin(), mm[0].end(), cmp);
  109.     vec[0].push_back(mm[0][0]);
  110.     int cur = 0;
  111.     last = 0;
  112.     int t = 1;
  113.     while(1) {
  114.         int er = 0;
  115.         while (t == mm[last].size()) {
  116.             ++last;
  117.             if (last >= mm.size()) {
  118.                 er = 1;
  119.                 break;
  120.             }
  121.             sort(mm[last].begin(), mm[last].end(), cmp);
  122.             ++cur;
  123.             vec[cur].push_back(mm[last][0]);
  124.             t = 1;
  125.         }
  126.         if (er)
  127.             break;
  128.         if (vec[cur][0].second/sq == mm[last][t].second/sq )
  129.             vec[cur].push_back(mm[last][t]);
  130.         else {
  131.             ++cur;
  132.             vec[cur].push_back(mm[last][t]);
  133.         }
  134.         ++t;
  135.     }
  136.     vec.resize(cur+1);
  137.  
  138.     for (auto &el : vec) {
  139.         ans = min(ans, dd(el));
  140.     }
  141.     cout << fixed << setprecision(8) << sqrt((double)ans) << "\n";
  142.  
  143.  
  144. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement