Pagini recente » Cod sursa (job #33921) | Cod sursa (job #3285281) | Cod sursa (job #2100756) | Cod sursa (job #1543570) | Cod sursa (job #1401961)
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
const int NMAX=100005;
typedef long long ll;
int n, i;
pair<ll,ll> vicx, vicy;
pair<ll,ll> sp[NMAX], p1[NMAX], p2[NMAX];
inline 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(dr-st<=1)
return 1LL<<60;
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-st)/2;
ll ans=min(divide_et_impera(st,med),divide_et_impera(med,dr));
int m=0, i, j;
for(i=st; i<=dr; i++)
if(abs(p2[i].second-p1[med].first)<=ans)
sp[++m]=p2[i];
m--;
for(i=0; i<m; i++)
for(j=i+1; j<=m&&j-i<=7; j++)
{
ans=min(ans,dist(sp[i],sp[j]));
//vicx=sp[i];
//vicy=sp[j];
}
return ans;
}
int main()
{
ifstream in("cmap.in");
ofstream out("cmap.out");
in>>n;
for(i=0; i<n; i++)
in>>p1[i].first>>p1[i].second;
sort(p1,p1+n);
for(i=0; i<n; i++)
p2[i]=make_pair(p1[i].second,p1[i].first);
out<<setprecision(6)<<fixed<<sqrt(divide_et_impera(0,n))<<'\n';
//out<<vicx.first<<' '<<vicx.second<<" "<<vicy.first<<' '<<vicy.second<<'\n';
return 0;
}