Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <vector>
- #include <map>
- #include <stack>
- #include <cmath>
- #include <set>
- #include <utility>
- #include <iomanip>
- #include <cstdlib>
- #include <ctime>
- #include <numeric>
- #include <unordered_map>
- using namespace std;
- long long dd(vector<pair<long long, long long> > & dop) {
- int c = dop.size();
- long long ans = 4000000000000000001;
- long long int dist = 0;
- for (int i = 0; i < c; ++i) {
- for (int j = i + 1; j < c; ++j) {
- long long de = (dop[i].first - dop[j].first) * (dop[i].first - dop[j].first) +
- (dop[i].second - dop[j].second) * (dop[i].second - dop[j].second);
- if (de >= ans)
- continue;
- for (int k = j + 1; k < c; ++k) {
- dist = de;
- dist = max(dist, (dop[i].first - dop[k].first) * (dop[i].first - dop[k].first) +
- (dop[i].second - dop[k].second) * (dop[i].second - dop[k].second));
- dist = max(dist, (dop[j].first - dop[k].first) * (dop[j].first - dop[k].first) +
- (dop[j].second - dop[k].second) * (dop[j].second - dop[k].second));
- ans = min(ans, dist);
- }
- }
- }
- return ans;
- }
- bool cmp(pair<long long, long long> p1, pair<long long, long long> p2) {
- return (p1.second < p2.second);
- }
- int main() {
- freopen("input.txt", "r", stdin);
- int n;
- cin >> n;
- vector<pair<long long, long long> > points(n);
- for (int i = 0; i < n; ++i) {
- cin >> points[i].first >> points[i].second;
- }
- random_shuffle(points.begin(), points.end());
- vector<int> used(n);
- int c = 500;
- c = min(c, n);
- vector<pair<long long, long long> > dop;
- if (c < 250) {
- for (int i = 0; i < c; ++i) {
- dop.push_back(points[i]);
- }
- } else
- for (int i = 0; i < c; ++i) {
- int e = rand() % n;
- if (used[e] == 0) {
- dop.push_back(points[e]);
- used[e] = 1;
- }
- }
- c = dop.size();
- long long int ans = 4000000000000000001;
- long long int dist = 0;
- for (int i = 0; i < c; ++i) {
- for (int j = i + 1; j < c; ++j) {
- long long de = (dop[i].first - dop[j].first) * (dop[i].first - dop[j].first) +
- (dop[i].second - dop[j].second) * (dop[i].second - dop[j].second);
- if (de >= ans)
- continue;
- for (int k = j + 1; k < c; ++k) {
- dist = de;
- dist = max(dist, (dop[i].first - dop[k].first) * (dop[i].first - dop[k].first) +
- (dop[i].second - dop[k].second) * (dop[i].second - dop[k].second));
- dist = max(dist, (dop[j].first - dop[k].first) * (dop[j].first - dop[k].first) +
- (dop[j].second - dop[k].second) * (dop[j].second - dop[k].second));
- ans = min(ans, dist);
- }
- }
- }
- sort(points.begin(), points.end());
- long long sq = static_cast<long long>(ceil(sqrt(ans)));
- sq*=2;
- vector<vector<pair<long long, long long> > > mm(n);
- vector<vector<pair<long long, long long> > > vec(n);
- mm[0].push_back(points[0]);
- int last = 0;
- for (int i = 1; i < n; ++i) {
- if (points[i].first/sq == mm[last][0].first/sq)
- mm[last].push_back(points[i]);
- else {
- ++last;
- mm[last].push_back(points[i]);
- }
- }
- mm.resize(last+1);
- sort(mm[0].begin(), mm[0].end(), cmp);
- vec[0].push_back(mm[0][0]);
- int cur = 0;
- last = 0;
- int t = 1;
- while(1) {
- int er = 0;
- while (t == mm[last].size()) {
- ++last;
- if (last >= mm.size()) {
- er = 1;
- break;
- }
- sort(mm[last].begin(), mm[last].end(), cmp);
- ++cur;
- vec[cur].push_back(mm[last][0]);
- t = 1;
- }
- if (er)
- break;
- if (vec[cur][0].second/sq == mm[last][t].second/sq )
- vec[cur].push_back(mm[last][t]);
- else {
- ++cur;
- vec[cur].push_back(mm[last][t]);
- }
- ++t;
- }
- vec.resize(cur+1);
- for (auto &el : vec) {
- ans = min(ans, dd(el));
- }
- cout << fixed << setprecision(8) << sqrt((double)ans) << "\n";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement