Pagini recente » Cod sursa (job #2937593) | Cod sursa (job #1559501) | Cod sursa (job #1531398) | Cod sursa (job #1064487) | Cod sursa (job #2969637)
using namespace std;
#ifdef EZ
#include "./ez/ez.h"
const string FILE_NAME = "test";
#else
#include <bits/stdc++.h>
const string FILE_NAME = "cmap";
#endif
#define mp make_pair
#define mt make_tuple
#define ll long long
#define pb push_back
#define fi first
#define se second
#define cin fin
#define cout fout
ifstream fin (FILE_NAME + ".in");
ofstream fout (FILE_NAME + ".out");
const int nMAX = 100e3;
int n;
pair<int, int> v[nMAX + 1];
long double dist(pair<int, int> A, pair<int, int> B)
{
return sqrt((long double) (A.fi-B.fi) * (A.fi-B.fi) + (long double) (A.se-B.se) * (A.se-B.se));
}
long double solve(int st, int dr)
{
if (dr-st+1 <= 3)
{
sort(v + st, v + dr+1, [](const pair<int, int> &A, const pair<int, int> &B) {
return A.se > B.se;
});
long double d = 9e15;
for (int i = st; i <= dr; ++i)
for (int j = i+1; j <= dr; ++j)
d = min(d, dist(v[i], v[j]));
return d;
}
vector<pair<int, int>> s1, s2;
int mj = st+dr >> 1;
int mjx = v[mj].fi;
long double d = min(solve(st, mj), solve(mj+1, dr));
vector<pair<int, int>> tmp(dr-st+1);
merge(v + st, v + mj+1, v + mj+1, v + dr+1, tmp.begin(), [](const pair<int, int> &A, const pair<int, int> &B) {
return A.se > B.se;
});
copy(tmp.begin(), tmp.end(), v + st);
vector<pair<int, int>> strip;
for (int i = st; i <= dr; ++i)
if (abs(mjx - v[i].fi) < d)
strip.pb(v[i]);
for (int i = 0; i < strip.size(); ++i)
for (int j = i+1; j < strip.size() && strip[i].se - strip[j].se < d; ++j)
d = min(d, dist(strip[i], strip[j]));
return d;
}
int main()
{
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> v[i].fi >> v[i].se;
sort(v + 1, v + n+1, [](const pair<int, int> &A, const pair<int, int> &B) {
return A.fi < B.fi;
});
cout << setprecision(15) << solve(1, n);
}