Pagini recente » Cod sursa (job #2270359) | Cod sursa (job #2751675) | Cod sursa (job #2023889) | Cod sursa (job #1067895) | Cod sursa (job #985216)
Cod sursa(job #985216)
#include <fstream>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <cmath>
#define maxn 100001
#define x first
#define y second
#define inf 1<<30
using namespace std;
ifstream fin ("cmap.in");
ofstream fout ("cmap.out");
typedef pair <double,double> point;
point v[maxn],aux[maxn],test[maxn];
int n;
inline bool cmp1 (const point &a, const point &b)
{
if (a.x==b.x) return a.y<b.y;
return a.x<b.x;
}
inline bool cmp2 (const point &a, const point &b)
{
if (a.y==b.y) return a.x<b.x;
return a.y<b.y;
}
inline double dist (const point &A, const point &B)
{
return sqrt ((A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y));
}
double closest_pair (int p, int q)
{
if (p==q) return inf;
if (p+1==q)
{
if (v[q].y<v[p].y) swap (v[p],v[q]);
return dist (v[p],v[q]);
}
int mid = (p+q)/2; double echelon = v[mid].x;
double D1 = closest_pair (p,mid);
double D2 = closest_pair (mid+1,q);
double D = min (D1,D2);
int t=0;
merge (v+p,v+mid+1,v+mid+1,v+q+1,aux+p,cmp2);
for (int i=p; i<=q ; ++i)
if (fabs(aux[i].x-echelon) < D) test[++t]=aux[i];
for (int i=1; i<=t; ++i)
for (int j=i+1; j<=i+7 && j<=t; ++j)
D = min (D,dist(test[i],test[j]) );
for (int i=p; i<=q; ++i) v[i]=aux[i];
return D;
}
int main()
{
fin>>n;
for (int i=1; i<=n; ++i) fin>>v[i].x>>v[i].y;
sort (v+1, v+n+1, cmp1);
double D = closest_pair (1,n);
fout<<fixed<<setprecision(7)<<D;
}