Pagini recente » Cod sursa (job #1285826) | Cod sursa (job #2334659) | Cod sursa (job #246831) | Cod sursa (job #1125628) | Cod sursa (job #1409637)
#include <fstream>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
int n,a,b;
vector<pair<int,int> >v;
double dist(pair<int,int> a, pair<int,int>b)
{
return sqrt(1ll*(a.first-b.first)*(a.first-b.first)+1ll*(a.second-b.second)*(a.second-b.second));
}
bool cmp(pair<int,int> a, pair<int,int> b)
{
if(a.second<b.second)
return true;
if(a.second==b.second)
if(a.first<b.first)
return true;
return false;
}
double solve(int l,int r)
{
if(l==r) return 1<<30;
if(r==l+1) return dist(v[l],v[r]);
int mij=(l+r)/2;
//divide et impera - o dreapta la mijloc ce imparte punctele in 2
double sol=min(solve(l,mij),solve(mij+1,r));
//cazul in care distanta minima este data de pct de o parte si de alta a dreptei,
//se formeaza un dreptunghi de lungime 2 sol si latime sol centrat pe dreapta respectiva
vector<pair<int,int> > aux;
for(int i=l;i<=r;++i)
{
if(abs(v[i].first-v[mij].first)<=sol) //pct la distanta mai mica de solutia actuala st si dr de dreapta
{
aux.push_back(v[i]);
}
}
sort(aux.begin(),aux.end(),cmp); //dupa y
for(int i=0;i<(int)aux.size();++i)
for(int j=1;j<=7;++j)
if(i+j<(int)aux.size())
if(dist(aux[i],aux[i+j])<sol)
sol=dist(aux[i],aux[i+j]);
return sol;
}
int main()
{
fin>>n;
for(int i=1;i<=n;++i)
{
fin>>a>>b;
v.push_back(make_pair(a,b));
}
sort(v.begin(),v.end());
fout<<fixed<<setprecision(6)<<solve(1,n);
return 0;
}