Pagini recente » Istoria paginii runda/aqweryuolnbc | Cod sursa (job #871576) | Istoria paginii runda/oni2014ziua1_11 | Cod sursa (job #1868817) | Cod sursa (job #2867938)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
vector<pair<int,int> > v;
int n;
double minim=1000000000;
vector<int> ver;
bool comp(pair<int,int> a, pair<int,int> b)
{
if(a.first!=b.first)return a.first< b.first;
else return a.second<b.second;
}
double distanta(int i, int j)
{
pair<int,int> a=v[i];
pair<int,int> b=v[j];
return sqrt((a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second));
}
bool compy(int i, int j)
{
return v[i].second<=v[j].second;
}
double comb(int s, int d)
{
int nr=0;
int mij=(s+d)/2;
//ver.resize(s-d+2);
for(int i=s; i<=d; i++)
{
if(abs(v[mij].first-v[i].first)<minim&&abs(v[mij].second-v[i].second)<minim)
{
ver[++nr]=i;
}
}
sort(ver.begin(),ver.end(),compy);
for(int i=1; i<=nr; i++)
{
for(int j=i+1; j<=nr&&j<=i+7; j++)
{
minim=min(minim,distanta(ver[i],ver[j]));
}
}
return minim;
}
double divide(int s, int d)
{
if(d-s>1)
{
if(d-s<=2)
{
minim=distanta(s,s+1);
if(d-s==2)
{
minim=min(minim,min(distanta(s+1,s+2),distanta(s,s+2)));
}
return minim;
}
int mij=(s+d)/2;
minim=min(divide(s,mij),divide(mij+1,d));
minim=min(minim,comb(s,d));
}
return minim;
}
int main()
{
fin>>n;
v.resize(n+1);
ver.resize(n+1);
for(int i=1; i<=n; i++)
{
fin>> v[i].first >> v[i].second;
}
sort(v.begin(),v.end(),comp);
divide(1,n);
fout<<setprecision(6)<<fixed<<minim;
return 0;
}