Pagini recente » Cod sursa (job #650561) | Cod sursa (job #109292) | Cod sursa (job #1493439) | Cod sursa (job #546219) | Cod sursa (job #3222195)
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
int n;
struct point
{
double x,y;
} a[1000005];
point v[1000005];
int comp(point a,point b)
{
return a.x<b.x || a.x==b.x && a.y<b.y;
}
int comp2(point a,point b)
{
return a.y<b.y || a.y==b.y && a.x<b.x;
}
double dist(point a,point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double divide(int st,int dr)
{
if (st==dr) return 2e9;
int mij=(st+dr)/2;
double d1=divide(st,mij);
double d2=divide(mij+1,dr);
double mn=min(d1,d2);
int t=0;
for (int i=st;i<=dr;i++)
{
if (abs(a[i].x-a[mij].x)<=mn) v[++t]=a[i];
}
sort (v+1,v+t+1,comp2);
for (int i=1;i<=t;i++)
for (int j=i+1;j<=t && dist(a[i],a[j])<=mn;j++)
{
mn=min(mn,dist(v[i],v[j]));
}
return mn;
}
int main()
{
fin>>n;
for (int i=1; i<=n; i++)
fin>>a[i].x>>a[i].y;
sort(a+1,a+n+1,comp);
fout<<fixed<<setprecision(6)<<divide(1,n);
return 0;
}