Pagini recente » Borderou de evaluare (job #1951275) | Borderou de evaluare (job #1393924) | Borderou de evaluare (job #1393966) | Borderou de evaluare (job #1198894) | Cod sursa (job #3317962)
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <iomanip>
using namespace std;
ifstream cin("cmap.in");
ofstream cout("cmap.out");
long long n,i;
double ras;
struct pct{
long long x;
long long y;
};
bool compar(pct a,pct b)
{
return (a.x<b.x) || (a.x==b.x && a.y>b.y);
}
bool compary(pct a,pct b)
{
return (a.y>b.y);
}
pct v[100005];
vector<pct>p;
double dist(pct a,pct b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void f(long long st,long long dr)
{
double m=0;
long long i,j;
if(dr-st==1)
{
m=dist(v[st],v[dr]);
if(m<ras)
{
ras=m;
}
return;
}
if(dr-st==2)
{
m=min(dist(v[st],v[st+1]),min(dist(v[st+1],v[st+2]),dist(v[st],v[st+2])));
if(m<ras)
{
ras=m;
}
return;
}
f(st,(st+dr)/2);
f((st+dr)/2,dr);
for(j=(st+dr)/2-1;j>=st;j--)
{
if(v[(st+dr)/2].x-v[j].x<ras)
p.push_back(v[j]);
else
break;
}
for(j=(st+dr)/2;j<=dr;j++)
{
if(v[j].x-v[(st+dr)/2].x<ras)
{
p.push_back(v[j]);
}
else
break;
}
sort(p.begin(),p.end(),compary);
long long l=p.size();
for(j=0;j<=l-1;j++)
{
for(i=j+1;i<=j+7 && i<l;i++)
{
if(dist(p[i],p[j])<ras)
{
ras=dist(p[i],p[j]);
}
}
}
p.clear();
}
int main()
{
ras=1e20;
cin>>n;
for(i=1;i<=n;i++)
{
cin>>v[i].x>>v[i].y;
}
sort(v+1,v+n+1,compar);
f(1,n);
cout<<fixed<<setprecision(10)<<ras;
return 0;
}