Pagini recente » Cod sursa (job #3189294) | Cod sursa (job #1621322) | Cod sursa (job #2226041) | Cod sursa (job #2705971) | Cod sursa (job #3230140)
//https://infoarena.ro/problema/cmap
#include <bits/stdc++.h>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
vector <pair<int,int>> v;
double dis=100000000;
bool compararex(pair<int,int> a,pair<int,int> b)
{
if(a.first<b.first)
return 1;
else
return 0;
}
bool compararey(pair<int,int> a,pair<int,int> b)
{
if(a.second<b.second)
return 1;
else
return 0;
}
double distanta(pair<int,int> a,pair<int,int> b)
{
return sqrt((a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second));
}
void recursivitate(int st,int dr)
{
if(st==dr)
return;
int mij,i,j;
mij=(st+dr)/2;
recursivitate(st,mij);
recursivitate(mij+1,dr);
vector <pair<int,int>> c;
for(i=st;i<=dr;++i)
{
if((v[i].first-v[mij].first)*(v[i].first-v[mij].first)<=dis*dis)
{
c.push_back(v[i]);
}
}
sort(c.begin(),c.end(),compararey);
for(i=0;i<c.size();++i)
{
for(j=i+1;((j<c.size())&&(c[j].second-c[i].second)*(c[j].second-c[i].second)<=dis*dis);++j)
{
if(dis>distanta(c[i],c[j]))
{
dis=distanta(c[i],c[j]);
}
}
}
}
int main()
{
int i,n,x,y;
fin>>n;
for(i=0;i<n;i++)
{
fin>>x>>y;
v.emplace_back(x,y);
}
sort(v.begin(),v.end(),compararex);
recursivitate(0,n-1);
fout<<fixed<<setprecision(6)<<dis;
// for(i=0;i<n;i++)
// {
// cout<<v[i].first<<" "<<v[i].second<<"\n";
// }
return 0;
}