Pagini recente » Cod sursa (job #1938055) | Cod sursa (job #23283) | Cod sursa (job #3227596) | Cod sursa (job #2141555) | Cod sursa (job #2490210)
#include <bits/stdc++.h>
#define pb push_back
#define uii unsigned int
#define ll long long
using namespace std;
vector <pair<ll,ll> > v;
ll dist(pair <ll,ll> a,pair<ll,ll> b)
{
ll p1x=a.first;
ll p1y=a.second;
ll p2x=b.first;
ll p2y=b.second;
return ((p1x-p2x)*(p1x-p2x)+(p1y-p2y)*(p1y-p2y));
}
ll divideEtImpera(ll st,ll dr)
{
ll mij,minL,minR;
ll d;
if(dr-st<=3)
{
ll minim=1e18;
uii i,j;
for(i=st;i<=dr;i++)
{
for(j=i+1;j<=dr;j++)
{
minim=min(minim,dist(v[i],v[j]));
}
}
return minim;
}
uii i,j;
mij=st+(dr-st)/2;
d=min(divideEtImpera(st,mij),divideEtImpera(mij+1,dr));
vector < pair<ll,ll> > new_v;
for(i=st;i<=dr;i++)
{
if(abs(v[mij].first-v[i].first)<d)
{
new_v.push_back({v[i].second,v[i].first});
}
}
sort(new_v.begin(),new_v.end());
for(i=0;i<new_v.size();i++)
{
for(j=i+1;j<new_v.size() && j < i + 8;j++)
{
ll new_d;
new_d=dist(new_v[i],new_v[j]);
if(new_d<d)
{
d=new_d;
}
}
}
return d;
}
int main()
{
ifstream fin("cmap.in");
ofstream fout("cmap.out");
int n,i,j;
ll a,b;
double f;
double min=999999999;
fin>>n;
for(i=1;i<=n;i++)
{
fin>>a>>b;
v.pb({a,b});
}
ll dist_best=1e9;
sort(v.begin(),v.end());
dist_best=divideEtImpera(0,n-1);
fout<<fixed<<setprecision(6)<<sqrt((double)dist_best);
fin.close();
fout.close();
return 0;
}