Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //#include <cassert>
- //
- ///** Begin fast allocation */
- //const int MAX_MEM = 2e8 + 6e7;
- //int mpos = 0;
- //char mem[MAX_MEM];
- //inline void * operator new (size_t n) {
- // assert((mpos += n) <= MAX_MEM);
- // return (void *)(mem + mpos - n);
- //}
- //void operator delete (void *) noexcePoint { } // must have!
- //void operator delete (void *, size_t) noexcePoint { } // must have!
- ///** End fast allocation */
- #pragma GCC optimize("Ofast")
- //#pragma GCC optimize ("unroll-loops")
- //#pragma GCC optimize ("fast-math")
- #pragma GCC target("avx2")
- //#include <bits/stdc++.h>
- #include <iostream>
- #include <algorithm>
- #include <string>
- #include <cmath>
- #include <vector>
- #include <map>
- #include <set>
- #include <list>
- #include <ctime>
- #include <stack>
- #include <queue>
- #include <iomanip>
- #include <cstdlib>
- #include <unordered_map>
- #include <unordered_set>
- #include <cstddef>
- #include <deque>
- #include <cstdio>
- #include <fstream>
- #include <random>
- #include <climits>
- #include <cassert>
- #include <chrono>
- #include <complex>
- using namespace std;
- #define forn(i, j, k) for(int i = (int)(j); i < (int)(k); i++)
- #define forn1(i, j, k) for(int i = (int)(j); i <= (int)(k); i++)
- #define pb push_back
- #define mp make_pair
- #define f first
- #define s second
- #define all(x) begin(x), end(x)
- #define sz(a) ((int)((a).size()))
- #define endl '\n'
- const int INF = 1e9 + 1;
- const long long MOD = 1'000'000'007;
- const long double EPS = 1e-9;
- typedef long long ll;
- typedef unsigned long long ull;
- typedef long double ld;
- std::mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
- struct hash_function {
- size_t operator() (const pair<int, int>& p) const {
- return p.first ^ p.second;
- }
- };
- int minx = INT_MAX, maxx = INT_MIN, miny = INT_MAX, maxy = INT_MIN;
- inline ld dist(pair<int, int>& a, pair<int, int>& b) {
- return sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
- }
- inline ld ans_for_points(pair<int, int>& a, pair<int, int>& b, pair<int, int>& c) {
- return max({dist(a, b), dist(a, c), dist(b, c)});
- }
- inline pair<int, int> get_bucket_num(pair<int, int> cord, ld d) {
- return {int(ld(cord.first - minx) / d + 1), int(ld(cord.second - miny) / d + 1)};
- }
- inline int get_bucket_(pair<int, int> cord_in_map, ld d) {
- return cord_in_map.first + cord_in_map.second * int((maxx - minx) / d + 2);
- }
- vector<int> get_num_buckets(pair<int, int> cord, ld d) {
- auto [x, y] = get_bucket_num(cord, d);
- return {
- get_bucket_({x - 1, y - 1}, d),
- get_bucket_({x, y - 1}, d),
- get_bucket_({x + 1, y - 1}, d),
- get_bucket_({x - 1, y}, d),
- get_bucket_({x, y}, d),
- get_bucket_({x + 1, y}, d),
- get_bucket_({x - 1, y + 1}, d),
- get_bucket_({x, y + 1}, d),
- get_bucket_({x + 1, y + 1}, d)
- };
- }
- void add_point(unordered_map<size_t, vector<int>>& map, ld d, int index, pair<int, int> cord) {
- int ind_in_map = get_bucket_(get_bucket_num(cord, d), d);
- map[ind_in_map].push_back(index);
- }
- void make_map(vector<pair<int, int>>& vec, int n, unordered_map<size_t, vector<int>>& map, ld d) {
- map.clear();
- for (int i = 0; i < n; ++i) {
- auto cord = vec[i];
- int ind_in_map = get_bucket_(get_bucket_num(cord, d), d);
- map[ind_in_map].push_back(i);
- }
- }
- void solve() {
- int n;
- cin >> n;
- vector<pair<int, int>> vec(n);
- for (auto& [x, y] : vec) {
- cin >> x >> y;
- minx = min(minx, x);
- miny = min(miny, y);
- maxx = max(maxx, x);
- maxy = max(maxy, y);
- }
- shuffle(vec.begin(), vec.end(), rnd);
- ld cur_ans = ans_for_points(vec[0], vec[1], vec[2]);
- unordered_map<size_t, vector<int>> map; // num of bucket : vector of indexes of points
- make_map(vec, 3, map, cur_ans);
- for (int i = 3; i < n; ++i) {
- vector<int> nums = get_num_buckets(vec[i], cur_ans);
- ld tmp_ans = cur_ans;
- vector<int> points;
- for (auto num : nums) {
- for (auto point : map[num]) {
- if (i != point) {
- points.push_back(point);
- }
- }
- }
- for (int j = 0; j < points.size() - 1; ++j) {
- for (int k = j + 1; k < points.size(); ++k) {
- tmp_ans = min(tmp_ans, ans_for_points(vec[i], vec[points[j]], vec[points[k]]));
- }
- }
- if (abs(cur_ans - tmp_ans) > EPS) {
- cur_ans = tmp_ans;
- make_map(vec, i + 1, map, cur_ans);
- } else {
- add_point(map, cur_ans, i, vec[i]);
- }
- }
- cout << cur_ans << endl;
- }
- int32_t main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- cout.precision(30);
- int testCases = 1;
- #ifdef LOCAL
- freopen("input.txt", "r", stdin);
- //freopen("output.txt", "w", stdout);
- cin >> testCases;
- #else
- //freopen("inputik.txt", "r", stdin);
- //freopen("outputik.txt", "w", stdout);
- testCases = 1;
- #endif
- while (testCases--) {
- solve();
- #ifdef LOCAL
- cout << "__________________________" << endl;
- #endif
- }
- #ifdef LOCAL
- cerr << endl << "finished in " << static_cast<double>(clock()) / CLOCKS_PER_SEC << " sec" << endl;
- #endif
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement