Pagini recente » Cod sursa (job #1215769) | Cod sursa (job #658888) | Cod sursa (job #2788226) | Cod sursa (job #345719) | Cod sursa (job #1160360)
#include<fstream>
#include<algorithm>
#include<iomanip>
#define Inf 10000000
#define Nmax 10001
using namespace std;
struct Point{
double x, y;
};
Point Puncte[Nmax];
int N,i;
double _distance(Point A, Point B)
{
return sqrt((A.x - B.x)*(A.x - B.x) + (A.y - B.y)*(A.y - B.y));
}
bool cmp(const Point& A, const Point& B)
{
if (A.x <= B.x)
return true;
return false;
}
bool cmp2(const Point& A, const Point& B)
{
if (A.y <= B.y)
return true;
return false;
}
double solve(int st, int dr)
{
if (dr - st + 1 <= 3)
{
int i, j;
double d = Inf;
for (i = st; i <= dr;++i)
for (j = st; j <= dr; ++j)
if (i!=j)
{
double tmp = _distance(Puncte[i], Puncte[j]);
d = min(d, tmp);
}
return d;
}
else
{
int m = (st + dr) / 2, k = 0;
Point A[Nmax];
double D1 = solve(st, m);
double D2 = solve(m + 1, dr);
double D = min(D1, D2), drp = (Puncte[m].x + Puncte[m + 1].x)/2;
i = m;
while (i >= 1 && Puncte[i].x >= drp - D)
{
A[k++] = Puncte[i--];
}
i = m + 1;
while (i <=dr && Puncte[i].x <= drp + D)
{
A[k++] = Puncte[i++];
}
sort(A + 1, A + 1 + k, cmp2);
for (int i = 1; i <= k;++i)
for (int j = i + 1; j <= min(k,i + 7); ++j)
D = min(D, _distance(Puncte[i], Puncte[j]));
return D;
}
}
int main()
{
freopen("cmap.in", "r", stdin);
freopen("cmap.out", "w", stdout);
scanf("%d", &N);
for (i = 1; i <= N; ++i)
scanf("%lf %lf", &Puncte[i].x, &Puncte[i].y);
sort(Puncte + 1, Puncte + N + 1, cmp);
double rez = solve(1, N);
printf("%.6lf\n", rez);
return 0;
}