Pagini recente » Cod sursa (job #2004899) | Cod sursa (job #2166163) | Cod sursa (job #281885) | Cod sursa (job #1808986) | Cod sursa (job #2582831)
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cmath>
#define MAX 100010
#define x first
#define y second
using namespace std;
typedef long double db;
typedef long long ll;
ll n;
pair<ll,ll> a[MAX],vp[MAX],va[MAX];
db dis(pair<ll,ll> p1, pair<ll,ll> p2){
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
bool cmp(pair<ll,ll> p1, pair<ll,ll> p2){
return p1.y<p2.y;
}
ll mod(ll nr){
return (nr>=0?nr:-nr);
}
void interclaseaza(ll st,ll dr,ll mij){
for(ll i=1,i1=st,i2=mij+1;i<=dr-st+1;i++){
if(i1==mij+1){
va[i]=vp[i2++];
continue;
}
if(i2==dr+1){
va[i]=vp[i1++];
continue;
}
if(cmp(vp[i1],vp[i2]))va[i]=vp[i1++];
else va[i]=vp[i2++];
}
for(ll i=1;i<=dr-st+1;i++)
vp[st+i-1]=va[i];
}
db rez(ll st,ll 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])));
sort(vp+st,vp+dr+1,cmp);
return ansa;
} else {
ll mij=(st+dr)/2;
db ans1=rez(st,mij);
db ans2=rez(mij+1,dr);
db ansa=min(ans1,ans2);
ll drd=a[mij].x;
interclaseaza(st,dr,mij);
// cout<<st<<" "<<dr<<" "<<ansa<<'\n';
// for(ll i=st;i<=dr;i++)cout<<vp[i].x<<" ";
// for(ll i=st;i<dr;i++)
// if(vp[i].y>vp[i+1].y)cout<<"fricc\n";
// cout<<"\n\n";
ll sz=0;
for(ll i=st;i<=dr;i++)
if(mod(vp[i].x-drd)<=ansa)va[++sz]=vp[i];
// cout<<sz<<'\n';
for(ll i=1;i<=sz;i++)
for(ll j=i+1;j<=i+7&&j<=sz;j++)
ansa=min(ansa,dis(va[i],va[j]));
return ansa;
}
}
int main()
{
ifstream f ("cmap.in");
ofstream g ("cmap.out");
f>>n;
for(ll i=1;i<=n;i++)
f>>a[i].x>>a[i].y,
vp[i]=a[i];
sort(a+1,a+n+1); sort(vp+1,vp+n+1);
g<<fixed<<setprecision(6)<<rez(1,n)<<'\n';
f.close ();
g.close ();
return 0;
}