Pagini recente » Cod sursa (job #635864) | Cod sursa (job #1189552) | Cod sursa (job #3037576) | Cod sursa (job #2776239) | Cod sursa (job #2582753)
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cmath>
#define MAX 100010
#define x first
#define y second
using namespace std;
typedef double db;
int n,sz;
pair<int,int> a[MAX],vp[MAX];
db dis(pair<int,int> p1, pair<int,int> p2){
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
bool cmp(pair<int,int> p1, pair<int,int> p2){
return p1.y<p2.y;
}
db rez(int st,int dr){
if(dr-st+1<=3){
db ansa;
ansa=dis(a[st],a[st+1]);
if(dr-st+1==3)
ansa=min(ansa,min(dis(a[st],a[dr]),dis(a[dr],a[dr-1])));
return ansa;
} else {
int mij=(st+dr)/2;
db ans1=rez(st,mij);
db ans2=rez(mij+1,dr);
db ansa=min(ans1,ans2);
int drd=a[mij].x;
sz=0;
for(int i=mij;a[i].x>=drd-ansa&&i>=0;i--) vp[++sz]=a[i];
for(int i=mij+1;a[i].x<=drd+ansa&&i<=n;i++) vp[++sz]=a[i];
sort(vp+1,vp+sz+1,cmp);
for(int i=1;i<=sz;i++)
for(int j=i+1;j<=i+7&&j<=sz;j++)
ansa=min(ansa,dis(vp[i],vp[j]));
return ansa;
}
}
int main()
{
ifstream f ("cmap.in");
ofstream g ("cmap.out");
f>>n;
for(int i=1;i<=n;i++)
f>>a[i].x>>a[i].y;
sort(a+1,a+n+1);
g<<fixed<<setprecision(6)<<rez(1,n)<<'\n';
f.close ();
g.close ();
return 0;
}