Pagini recente » Cod sursa (job #2947634) | Cod sursa (job #1610608) | Monitorul de evaluare | Cod sursa (job #1847105) | Cod sursa (job #1515700)
#include<cstdio>
#include<fstream>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<cmath>
#define DIM 100002
#define INF (1LL << 60)
#define Minim(x, y) (x <= y ? x : y)
using namespace std;
int N;
vector < pair<int, int> > v;
pair <int, int> w[DIM];
int NR;
inline long long dist(const pair <int, int>& a, const pair <int, int>& b)
{
return 1LL * (a.first - b.first) * (a.first - b.first) + 1LL * (a.second - b.second) * (a.second - b.second);
}
long long Solve (int, int);
int main()
{
ifstream f("cmap.in");
ofstream g("cmap.out");
f >> N;
for (int i = 1; i <= N; ++i)
{
v.push_back(make_pair(0, 0));
f >> v.back().first >> v.back().second;
}
sort (v.begin(), v.end());
g << fixed << setprecision(7) << sqrt(1.0L * Solve(0, int(v.size()) - 1)) << '\n';
}
long long Solve(int left, int right)
{
if (left == right)
return INF;
if (right - left == 1)
return dist(v[left], v[right]);
int mid = (left + right) >> 1;
int X = v[mid].first;
long long d1 = Solve(left, mid), d2 = Solve(mid + 1, right);
long long dmin = Minim(d1, d2);
NR = 0;
for (int i = left; i <= right; ++i)
if (v[i].first >= X - dmin && v[i].first <= X + dmin)
w[++NR] = make_pair(v[i].second, v[i].first);
sort (w + 1, w + NR + 1);
for (int i = 1; i <= NR; ++i)
for (int j = 1; i + j <= NR && j <= 7; ++j)
dmin = Minim(dmin, dist(w[i], w[i + j]));
return dmin;
}