Pagini recente » Cod sursa (job #2849581) | Cod sursa (job #2946232) | Cod sursa (job #2835533) | Cod sursa (job #1108187) | Cod sursa (job #2462276)
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>
#define xx first
#define yy second
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
int n,i;
pair<int, int> v[100005],aux[100005];
int dist(pair<int, int> a, pair<int, int> b)
{ return (a.xx-b.xx)*(a.xx-b.xx)+(a.yy-b.yy)*(a.yy-b.yy); }
void interclasare(int st, int mid, int dr)
{
int i = st; int j = mid+1; int k = 0;
while (i <= mid && j <= dr)
if (v[i].yy <= v[j].yy)
aux[++k] = v[i++];
else
aux[++k] = v[j++];
for (;i<=mid; i++)
aux[++k] = v[i];
for (;j<=dr; j++)
aux[++k] = v[j];
for (int i=st; i<=dr; i++)
v[i] = aux[i-st+1];
}
int solve(int st, int dr)
{
int mid = (st+dr)/2;
if (dr-st == 1)
{
interclasare(st, mid, dr);
return dist(v[st], v[dr]);
}
if (dr-st == 2)
{
interclasare(st, st, mid); interclasare(st, mid, dr);
return min(dist(v[st+1], v[st+2]), min(dist(v[st], v[st+1]), dist(v[st], v[st+2])));
}
int sols = solve(st, mid);
int sold = solve(mid+1, dr);
int sol = min(sols, sold);
interclasare(st, mid, dr);
for (int i=st; i<dr; i++)
for (int j=i+1; j<=max(dr, i+7); j++)
sol = min(sol, dist(v[i], v[j]));
return sol;
}
int main()
{
fin >> n;
for (i=1; i<=n; i++)
fin >> v[i].xx >> v[i].yy;
sort(v+1, v+n+1);
fout << setprecision(7) << fixed << sqrt(solve(1, n));
return 0;
}