Pagini recente » Cod sursa (job #2204626) | Cod sursa (job #1672099) | Cod sursa (job #1706350) | Cod sursa (job #843321) | Cod sursa (job #757437)
Cod sursa(job #757437)
#include <cstdio>
#include <vector>
#include <limits>
#include <algorithm>
#include <cmath>
using namespace std;
int N;
vector< pair<double, double> > P;
inline double dist(int i, int j)
{
return sqrtl(pow(P[i].first - P[j].first, 2) + pow(P[i].second - P[j].second, 2));
}
double mind(int i, int j)
{
double a = numeric_limits<double>::max(), d;
if (j - i <= 2)
{
for (int l = i; l < j; ++l)
{
for (int m = l + 1; m <= j; ++m)
{
d = dist(l, m);
a = d < a - numeric_limits<double>::epsilon()? d: a;
}
}
vector< pair<double, double> > X;
for (int l = i; l <= j; ++l)
{
X.push_back(make_pair(P[l].second, P[l].first));
}
sort(X.begin(), X.end());
for (int l = 0; l <= j - i; ++l)
{
P[l + i].first = X[l].second;
P[l + i].second = X[l].first;
}
return a;
}
int l, m, t = (i + j) / 2;
d = (P[t].first + P[t + 1].first) / 2;
double left = mind(i, t);
double rite = mind(t + 1, j);
double s = left < rite - numeric_limits<double>::epsilon()? left: rite;
vector< pair<double, double> > X;
for (l = i, m = t + 1; l <= t && m <= j;)
{
if (P[l].second < P[m].second - numeric_limits<double>::epsilon())
{
X.push_back(make_pair(P[l].first, P[l].second));
++l;
}
else
{
X.push_back(make_pair(P[m].first, P[m].second));
++m;
}
}
while (l <= t)
{
X.push_back(make_pair(P[l].first, P[l].second));
++l;
}
while (m <= j)
{
X.push_back(make_pair(P[m].first, P[m].second));
++m;
}
vector< pair<double, double> > Y;
for (t = 0; t <= j - i; ++t)
{
P[t + i].first = X[t].first;
P[t + i].second = X[t].second;
if (fabs(X[t].first - d) < s + numeric_limits<double>::epsilon())
{
Y.push_back(make_pair(X[t].first, X[t].second));
}
}
t = Y.size();
for (l = 0; l < t; ++l)
{
for (m = l + 1; m < l + 8 && m < t; ++m)
{
d = dist(l, m);
a = d < a - numeric_limits<double>::epsilon()? d: a;
}
}
return a < s - numeric_limits<double>::epsilon()? a: s;
}
int main()
{
int i;
double x, y;
freopen("cmap.in", "r", stdin);
freopen("cmap.out", "w", stdout);
scanf("%d", &N);
for (i = 0; i < N; ++i)
{
scanf("%lf%lf", &x, &y);
P.push_back(make_pair(x, y));
}
sort(P.begin(), P.end());
printf("%lf\n", mind(0, N - 1));
return 0;
}