Pagini recente » Cod sursa (job #2436176) | Cod sursa (job #1934804) | Cod sursa (job #519372) | Cod sursa (job #1166413) | Cod sursa (job #1160364)
#include<fstream>
#include<algorithm>
#include<iomanip>
#define Inf 10000000
#define Nmax 100001
using namespace std;
struct Point{
double x, y;
};
Point Puncte[Nmax];
Point A[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;
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);
ifstream fin("cmap.in");
ofstream fout("cmap.out");
fin >> N;
for (i = 1; i <= N; ++i)
fin >> Puncte[i].x>>Puncte[i].y;
sort(Puncte + 1, Puncte + N + 1, cmp);
fout << fixed << setprecision(6) << solve(1, N) << '\n';
return 0;
}