Pagini recente » Cod sursa (job #1417022) | Cod sursa (job #2036549) | Cod sursa (job #699239) | Cod sursa (job #1927730) | Cod sursa (job #1027028)
#include<iostream>
#include<fstream>
#include<vector>
#include<cmath>
#include<algorithm>
#include<cstdio>
using namespace std;
ifstream f("cmap.in");
FILE *g = fopen("cmap.out","w");
typedef struct Compare
{
bool operator() (const pair<int,int> a,const pair<int,int> b)
{
if(a.second == b.second)
return a.first < b.first;
return a.second < b.second;
}
} ICompare;
#define MaxN 100100
#define mid ((li+ls)>>1)
#define pint pair<double,double>
int N;
double Sol;
vector<pair<double,double> > A;
vector<pair<double,double> > Y;
void citire(void)
{
int x,y;
f >> N;
for(int i=1;i<=N;i++)
{
f >> x >> y;
A.push_back(make_pair(x,y));
}
}
inline double dist(pint a,pint b)
{
return sqrt((a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second));
}
inline double getDist(pint a,pint b,pint c)
{
return min(dist(a,b),min(dist(a,c),dist(b,c)));
}
inline double DEI(int li,int ls)
{
if(ls-li == 1)
return dist(A[li],A[ls]);
else if(ls-li == 2)
return getDist(A[li],A[li+1],A[ls]);
double dis = DEI(li,mid);
dis = min(dis,DEI(mid+1,ls));
Y.clear();
for(int i=mid;i>=li && A[mid].first-A[i].first <= dis;i--)
Y.push_back(A[i]);
for(int i=mid+1;i <= ls && A[i].first-A[mid].first <= dis;i++)
Y.push_back(A[i]);
sort(Y.begin(),Y.end(),ICompare());
for(int i=0;i<Y.size();i++)
for(int j=i+1;j<Y.size() && j<i+8;j++)
dis = min(dis,dist(Y[i],Y[j]));
return dis;
}
void Rezolvare(void)
{
sort(A.begin(),A.end());
Sol = DEI(0,N-1);
}
int main()
{
citire();
Rezolvare();
fprintf(g,"%.6lf\n",Sol);
}