Advertisement
playerr17

Untitled

Oct 27th, 2023 (edited)
1,567
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //#include <cassert>
  2. //
  3. ///** Begin fast allocation */
  4. //const int MAX_MEM = 2e8 + 6e7;
  5. //int mpos = 0;
  6. //char mem[MAX_MEM];
  7. //inline void * operator new (size_t n) {
  8. //    assert((mpos += n) <= MAX_MEM);
  9. //    return (void *)(mem + mpos - n);
  10. //}
  11. //void operator delete (void *) noexcePoint { } // must have!
  12. //void operator delete (void *, size_t) noexcePoint { } // must have!
  13. ///** End fast allocation */
  14. #pragma GCC optimize("Ofast")
  15. //#pragma GCC optimize ("unroll-loops")
  16. //#pragma GCC optimize ("fast-math")
  17. #pragma GCC target("avx2")
  18. //#include <bits/stdc++.h>
  19. #include <iostream>
  20. #include <algorithm>
  21. #include <string>
  22. #include <cmath>
  23. #include <vector>
  24. #include <map>
  25. #include <set>
  26. #include <list>
  27. #include <ctime>
  28. #include <stack>
  29. #include <queue>
  30. #include <iomanip>
  31. #include <cstdlib>
  32. #include <unordered_map>
  33. #include <unordered_set>
  34. #include <cstddef>
  35. #include <deque>
  36. #include <cstdio>
  37. #include <fstream>
  38. #include <random>
  39. #include <climits>
  40. #include <cassert>
  41. #include <chrono>
  42. #include <complex>
  43.  
  44. using namespace std;
  45. #define forn(i, j, k) for(int i = (int)(j); i < (int)(k); i++)
  46. #define forn1(i, j, k) for(int i = (int)(j); i <= (int)(k); i++)
  47. #define pb push_back
  48. #define mp make_pair
  49. #define f first
  50. #define s second
  51. #define all(x) begin(x), end(x)
  52. #define sz(a) ((int)((a).size()))
  53. #define endl '\n'
  54. const int INF = 1e9 + 1;
  55. const long long MOD = 1'000'000'007;
  56. const long double EPS = 1e-9;
  57. typedef long long ll;
  58. typedef unsigned long long ull;
  59. typedef long double ld;
  60. std::mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
  61. struct hash_function {
  62.    size_t operator() (const pair<int, int>& p) const {
  63.        return p.first ^ p.second;
  64.    }
  65. };
  66.  
  67. int minx = INT_MAX, maxx = INT_MIN, miny = INT_MAX, maxy = INT_MIN;
  68.  
  69. inline ld dist(pair<int, int>& a, pair<int, int>& b) {
  70.    return sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
  71. }
  72.  
  73. inline ld ans_for_points(pair<int, int>& a, pair<int, int>& b, pair<int, int>& c) {
  74.    return max({dist(a, b), dist(a, c), dist(b, c)});
  75. }
  76.  
  77. inline pair<int, int> get_bucket_num(pair<int, int> cord, ld d) {
  78.    return {int(ld(cord.first - minx) / d  + 1), int(ld(cord.second - miny) / d  + 1)};
  79. }
  80.  
  81. inline int get_bucket_(pair<int, int> cord_in_map, ld d) {
  82.    return cord_in_map.first + cord_in_map.second * int((maxx - minx) / d + 2);
  83. }
  84.  
  85. vector<int> get_num_buckets(pair<int, int> cord, ld d) {
  86.    auto [x, y] = get_bucket_num(cord, d);
  87.    return {
  88.            get_bucket_({x - 1, y - 1}, d),
  89.            get_bucket_({x, y - 1}, d),
  90.            get_bucket_({x + 1, y - 1}, d),
  91.  
  92.            get_bucket_({x - 1, y}, d),
  93.            get_bucket_({x, y}, d),
  94.            get_bucket_({x + 1, y}, d),
  95.  
  96.            get_bucket_({x - 1, y + 1}, d),
  97.            get_bucket_({x, y + 1}, d),
  98.            get_bucket_({x + 1, y + 1}, d)
  99.    };
  100. }
  101.  
  102. void add_point(unordered_map<size_t, vector<int>>& map, ld d, int index, pair<int, int> cord) {
  103.    int ind_in_map = get_bucket_(get_bucket_num(cord, d), d);
  104.    map[ind_in_map].push_back(index);
  105. }
  106.  
  107. void make_map(vector<pair<int, int>>& vec, int n, unordered_map<size_t, vector<int>>& map, ld d) {
  108.    map.clear();
  109.    for (int i = 0; i < n; ++i) {
  110.        auto cord = vec[i];
  111.        int ind_in_map = get_bucket_(get_bucket_num(cord, d), d);
  112.        map[ind_in_map].push_back(i);
  113.    }
  114. }
  115.  
  116. void solve() {
  117.    int n;
  118.    cin >> n;
  119.    vector<pair<int, int>> vec(n);
  120.    for (auto& [x, y] : vec) {
  121.        cin >> x >> y;
  122.  
  123.        minx = min(minx, x);
  124.        miny = min(miny, y);
  125.  
  126.        maxx = max(maxx, x);
  127.        maxy = max(maxy, y);
  128.    }
  129.    shuffle(vec.begin(), vec.end(), rnd);
  130.  
  131.    ld cur_ans = ans_for_points(vec[0], vec[1], vec[2]);
  132.    unordered_map<size_t, vector<int>> map; // num of bucket : vector of indexes of points
  133.  
  134.    make_map(vec, 3, map, cur_ans);
  135.  
  136.    for (int i = 3; i < n; ++i) {
  137.        vector<int> nums = get_num_buckets(vec[i], cur_ans);
  138.        ld tmp_ans = cur_ans;
  139.        vector<int> points;
  140.        for (auto num : nums) {
  141.            for (auto point : map[num]) {
  142.                if (i != point) {
  143.                    points.push_back(point);
  144.                }
  145.            }
  146.        }
  147.  
  148.        for (int j = 0; j < points.size() - 1; ++j) {
  149.            for (int k = j + 1; k < points.size(); ++k) {
  150.                tmp_ans = min(tmp_ans, ans_for_points(vec[i], vec[points[j]], vec[points[k]]));
  151.            }
  152.        }
  153.  
  154.        if (abs(cur_ans - tmp_ans) > EPS) {
  155.            cur_ans = tmp_ans;
  156.            make_map(vec, i + 1, map, cur_ans);
  157.        } else {
  158.            add_point(map, cur_ans, i, vec[i]);
  159.        }
  160.    }
  161.  
  162.    cout << cur_ans << endl;
  163. }
  164.  
  165. int32_t main() {
  166.    ios_base::sync_with_stdio(false);
  167.    cin.tie(nullptr);
  168.    cout.tie(nullptr);
  169.    cout.precision(30);
  170.    int testCases = 1;
  171. #ifdef LOCAL
  172.    freopen("input.txt", "r", stdin);
  173.    //freopen("output.txt", "w", stdout);
  174.    cin >> testCases;
  175. #else
  176.    //freopen("inputik.txt", "r", stdin);
  177.    //freopen("outputik.txt", "w", stdout);
  178.    testCases = 1;
  179. #endif
  180.    while (testCases--) {
  181.        solve();
  182. #ifdef LOCAL
  183.        cout << "__________________________" << endl;
  184. #endif
  185.    }
  186. #ifdef LOCAL
  187.    cerr << endl << "finished in " << static_cast<double>(clock()) / CLOCKS_PER_SEC << " sec" << endl;
  188. #endif
  189.    return 0;
  190. }
  191.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement