Pagini recente » Cod sursa (job #2890537) | Cod sursa (job #1854758) | Cod sursa (job #2068888) | Cod sursa (job #1300258) | Cod sursa (job #3037894)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <vector>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
struct Pct{
double i, j;
}x[100001];
bool C(Pct a, Pct b)
{if(a.i<b.i || (a.i==b.i && a.j<b.j))return 1;
return 0;
}
double Dist(double x1, double y1, double x2, double y2)
{double a=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
return a;
}
long double DQ(int st, int dr)
{if(dr-st+1<=3)
{double mini=1e9;
for(int i=st;i<dr;i++)
for(int j=i+1;j<=dr;j++)
mini=min(mini, Dist(x[i].i, x[i].j, x[j].i, x[j].j));
return mini;
}
else
{int mij=(st+dr)/2;
double mini=min(DQ(st, mij), DQ(mij+1, dr));
vector<Pct> y;
for(int i=st;i<=dr;i++)
if(abs(x[i].i-x[mij].i)<=mini)y.push_back(x[i]);
for(int i=0;i<y.size()-1;i++)
for(int j=i+1;j<y.size();j++)
mini=min(mini, Dist(y[i].i, y[i].j, y[j].i, y[j].j));
return mini;
}
}
int main()
{ int n;
fin>>n;
for(int i=1;i<=n;i++)
fin>>x[i].i>>x[i].j;
sort(x+1, x+1+n, C);
DQ(1, n);
fout<<fixed<<setprecision(6)<<DQ(1, n);
return 0;
}