Pagini recente » Cod sursa (job #3286278) | Cod sursa (job #3193717) | Profil Barbu_Matei | Cod sursa (job #1935057) | Cod sursa (job #3292984)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
const int lim=1e5;
int n,i;
double t;
struct punct
{
double x,y;
}v[lim+10];
bool cmp(punct a,punct b)
{
return a.x<b.x;
}
bool cmpi(punct a,punct b)
{
return a.y<b.y;
}
double dist(int x,int y,int x2,int y2)
{
return ((x-x2)*(x-x2)+(y-y2)*(y-y2));
}
void solve(int st,int dr)
{
if(st==dr)
return;
int mid=(st+dr)/2,i,x=v[mid].x,j;
solve(st,mid);
solve(mid+1,dr);
vector <punct> a;
for(i=st;i<=dr;i++)
{
if((v[i].x-x)*(v[i].x-x)<=t)
a.push_back(v[i]);
else break;
}
sort(a.begin(),a.end(),cmpi);
int l=a.size();
for(i=0;i<l-1;i++)
for(j=i+1;j<l;j++)
{
if((a[i].y-a[j].y)*(a[i].y-a[j].y)>t)break;
t=min(t,dist(a[i].x,a[i].y,a[j].x,a[j].y));
}
}
int main()
{
fin>>n;
for(i=1;i<=n;i++)
{
fin>>v[i].x>>v[i].y;
}
sort(v+1,v+n+1,cmp);
t=1e18;
solve(1,n);
t=sqrt(t);
fout<<fixed<<setprecision(6)<<t;
return 0;
}