Pagini recente » Cod sursa (job #2349879) | Cod sursa (job #2351041) | Cod sursa (job #130396) | Cod sursa (job #2356576) | Cod sursa (job #2194554)
#include <bits/stdc++.h>
#define INF 1e15
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
vector<pair<long long,long long> >points;
vector<long long>lines;
vector<long long>::iterator low,up;
int n,x,y;
bool cmp(pair<long long,long long>a,pair<long long,long long>b)
{
if(a.first==b.first)
return a.second<b.second;
return a.first<b.first;
}
long double divide(int pos1,int pos2)
{
if(pos2-pos1>2)
{
long double s=min(divide(pos1,(pos1+pos2)/2),divide((pos1+pos2)/2+1,pos2));
long long minpoint=points[(pos1+pos2)/2].first-s;
long long maxpoint=points[(pos1+pos2)/2].first+s+1;
low=lower_bound(lines.begin()+pos1,lines.begin()+pos2,minpoint);
up=upper_bound(lines.begin()+pos1,lines.begin()+pos2,maxpoint)-1;
int p1=low-lines.begin();
int p2=up-lines.begin();
for(int i=p1;i<=p2-1;i++)
for(int j=i+1;j<=p2;j++)
if(sqrt((points[i].first-points[j].first)*(points[i].first-points[j].first)+(points[i].second-points[j].second)*(points[i].second-points[j].second))<s)
s=sqrt((points[i].first-points[j].first)*(points[i].first-points[j].first)+(points[i].second-points[j].second)*(points[i].second-points[j].second));
return s;
}
long double mn=INF;
for(int i=pos1;i<=pos2-1;i++)
for(int j=i+1;j<=pos2;j++)
if(sqrt((points[i].first-points[j].first)*(points[i].first-points[j].first)+(points[i].second-points[j].second)*(points[i].second-points[j].second))<mn)
mn=sqrt((points[i].first-points[j].first)*(points[i].first-points[j].first)+(points[i].second-points[j].second)*(points[i].second-points[j].second));
return mn;
}
int main()
{
fin>>n;
for(int i=1;i<=n;i++)
{
fin>>x>>y;
points.push_back({x,y});
}
sort(points.begin(),points.end(),cmp);
for(int i=0;i<n;i++)
lines.push_back(points[i].first);
fout<<setprecision(7);
fout<<fixed;
fout<<divide(0,n-1);
return 0;
}