Pagini recente » Cod sursa (job #2137230) | Cod sursa (job #1296701) | Cod sursa (job #3171217) | Cod sursa (job #1186563) | Cod sursa (job #1400873)
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
const int NMAX=100005;
typedef long long ll;
const ll inf=2e40;
int n, i;
vector< pair<ll,ll> > sp(NMAX), p1, p2;
ll dist(const pair<ll,ll>& a,const pair<ll,ll>& b)
{
return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second);
}
ll divide_et_impera(int st,int dr)
{
if(st-dr>=-1)
return inf;
if(dr-st==2)
{
if(p2[st]>p2[st+1])
swap(p2[st],p2[st+1]);
return dist(p1[st],p1[st+1]);
}
int med=(st+dr)>>1;
ll ans=min(divide_et_impera(st,med),divide_et_impera(med,dr));
merge(p2.begin()+st,p2.begin()+med,p2.begin()+med,p2.begin()+dr,sp.begin());
copy(sp.begin(),sp.begin()+dr-st,p2.begin()+st);
int m=0, i, j;
for(i=st; i<=dr; i++)
if(abs(p2[i].second-p1[med].first)<=ans)
sp[++m]=p2[i];
for(i=1; i<=m; i++)
for(j=i+1; j<m&&j-i==7; j++)
ans=min(ans,dist(sp[i],sp[j]));
return ans;
}
int main()
{
ifstream in("cmap.in");
ofstream out("cmap.out");
in>>n;
p1.resize(n);
p2.resize(n);
for(i=0; i<p1.size(); i++)
in>>p1[i].first>>p1[i].second;
sort(p1.begin(),p1.end());
for(i=0; i<p1.size(); i++)
p2[i]=make_pair(p1[i].second,p1[i].first);
out<<setprecision(7)<<fixed<<sqrt(divide_et_impera(0,n))<<'\n';
return 0;
}