Pagini recente » Cod sursa (job #2693963) | Cod sursa (job #2318087) | Cod sursa (job #2986640) | Cod sursa (job #7072) | Cod sursa (job #3292506)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <vector>
#define int long long
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
const int MAX=1e5;
int n,i;
pair <int,int> p[MAX+5];
int dist(pair<int,int> a, pair<int,int> b)
{
return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second);
}
bool compare(pair<int,int> a, pair<int,int> b)
{
return a.first<b.first;
}
bool compare2(pair<int,int> a, pair<int,int> b)
{
return a.second<b.second;
}
long double ans=1e18;
void solve(int st ,int dr)
{
if (st==dr)
return;
int mij=(st+dr)>>1,x=p[mij].first,i,j;
long double distanta;
vector <pair <int,int > > pct;
solve(st,mij);
solve(mij+1,dr);
for (i=st; i<=dr; i++)
{
if ((x-p[i].first)*(x-p[i].first)<=ans)
pct.push_back(p[i]);
}
sort(pct.begin(),pct.end(),compare2);
for (i=0; i<pct.size(); i++)
{
for (j=i+1; j<pct.size(); j++)
{
if ((pct[i].second-pct[j].second)*(pct[i].second-pct[j].second)>ans)
break;
distanta=dist(pct[i],pct[j]);
ans=min(ans,distanta);
}
}
}
signed main()
{
fin>>n;
for (i=1; i<=n; i++)
fin>>p[i].first>>p[i].second;
sort(p+1,p+n+1,compare);
solve(1,n);
ans=sqrt(ans);
fout<<fixed<<setprecision(7)<<ans;
return 0;
}