Pagini recente » Cod sursa (job #2647657) | Cod sursa (job #394070) | Cod sursa (job #238988) | Cod sursa (job #2374114) | Cod sursa (job #2875163)
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
long long dist(pair <long long,long long> x,pair <long long,long long> y)
{
return (x.first-y.first)*(x.first-y.first)+(x.second-y.second)*(x.second-y.second);
}
long long INF=4e18;
vector <pair<long long,long long>> v(100005);
long long divide(int st,int dr,vector <pair<long long,long long>> &a,vector <pair<long long,long long>> &b)
{
if(st>=dr-1)
return INF;
if(dr-st==2)
{
if(b[st]>b[st+1])
swap(b[st],b[st+1]);
return dist(a[st],a[st+1]);
}
int mid=(st+dr)/2;
long long sol=min(divide(st,mid,a,b),divide(mid,dr,a,b));
merge(b.begin()+st,b.begin()+mid,b.begin()+mid,b.begin()+dr,v.begin());
copy(v.begin(),v.begin()+(dr-st),b.begin()+st);
v.clear();
for(int i=st;i<dr;i++)
if(abs(b[i].second-a[mid].first)<=sol)
v.push_back(b[i]);
for(int i=0;i<v.size()-1;i++)
for(int j=i+1;j<v.size() && j-i<8;j++)
sol=min(sol,dist(v[i],v[j]));
return sol;
}
vector <pair<long long,long long>> a,b;
long long x,y;
int n,i;
int main()
{
f>>n;
for(i=1;i<=n;i++)
{
f>>x>>y;
a.push_back(make_pair(x,y));
}
sort(a.begin(),a.end());
for(i=0;i<n;i++)
b.push_back(a[i]);
g<<fixed<<setprecision(6)<<sqrt(divide(0,n,a,b));
return 0;
}