Pagini recente » Cod sursa (job #1071318) | Cod sursa (job #563060) | Cod sursa (job #2110352) | Cod sursa (job #172246) | Cod sursa (job #1675940)
#include <fstream>
#include <climits>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iomanip>
#define punct pair<int,int>
#define x first
#define y second
using namespace std;
vector <punct> X,Y,z;
punct v[100005];
double modul (double x)
{
if (x<0) return -x;
return x;
}
inline double dist(punct A, punct B)
{
return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
double dei(int st, int dr, vector <punct> & X, vector <punct> & Y)
{
double dmin=INT_MAX;
int i,j;
if (dr-st+1<=3)
{
if (st==dr) return dmin;
for (i=st;i<dr;i++)
for (j=i+1;j<=dr;j++)
dmin=min(dmin,dist(Y[i],Y[j]));
return dmin;
}
else
{
int mitte=(st+dr)/2;
dmin=min(dei(st,mitte,X,Y),dei(mitte+1,dr,X,Y));
merge(Y.begin()+st,Y.begin()+mitte,Y.begin()+mitte,Y.begin()+dr,v);//se toarna in v;
for (i=st;i<dr;i++)
{
Y[i]=v[i-st];
if (modul(X[mitte].x-Y[i].x)<=dmin) z.push_back(Y[i]);
}
for (i=0;i<z.size();i++)
for (j=i+1;j<z.size()&&j<i+8;j++)
dmin=min(dmin,dist(z[i],z[j]));
z.clear();
return dmin;
}
}
int main()
{
ifstream f("cmap.in");
ofstream g("cmap.out");
int n,i;double dmin;
f>>n;punct p;
for (i=1;i<=n;i++)
{
f>>p.x>>p.y;
X.push_back(p);
}
sort(X.begin(),X.end());
for (i=0;i<n;i++)
Y.push_back(make_pair(X[i].y,X[i].x));
dmin=dei(0,n-1,X,Y);
g<<fixed<<setprecision(6);
g<<dmin<<'\n';
f.close();
g.close();
return 0;
}