Pagini recente » Cod sursa (job #1964443) | Cod sursa (job #812556) | Istoria paginii runda/concursulalablanao | Cod sursa (job #1895392) | Cod sursa (job #2119606)
#include<iostream>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<iomanip>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
double s;
int n,i,j,li,ls;
struct pnct
{ int x,y; } p[100005], yul[100005];
bool cord(pnct x,pnct y)
{ return x.y<y.y; }
bool cabs(pnct x,pnct y)
{ return x.x<y.x; }
double dis(pnct a,pnct b)
{
long long x=abs(a.x-b.x), y=abs(a.y-b.y);
return sqrt(x*x+y*y);
}
double cmap(int st,int dr)
{
int i,j,li;
double s=0.0,mx=0.0;
if(dr-st<3)
{
mx=dis(p[st],p[st+1]);
for(i=st;i<dr;i++)
for(j=i+1;j<=dr;j++)
{
s=dis(p[i],p[j]);
if(s<mx) mx=s;
}
return mx;
}
li=(st+dr)/2;
mx=cmap(st,li);
mx=min(mx,cmap(li+1,dr));
pnct ox[dr-st+1];
int dd=p[li].x,nre=0;
for(i=st;i<=dr;i++)
if(double(abs(yul[i].x-dd))<=s)
{
nre++;
ox[nre]=yul[i];
}
for(i=1;i<nre;i++)
for(j=i+1;j<=i+7;j++)
{
s=dis(ox[i],ox[j]);
if(s<mx) mx=s;
}
return mx;
}
int main () {
fin>>n;
for(i=1;i<=n;i++)
{
fin>>p[i].x>>p[i].y;
yul[i]=p[i];
}
sort(p+1,p+n+1,cabs);
sort(yul+1,yul+n+1,cord);
s=cmap(1,n);
fout<<fixed<<setprecision(6)<<s<<"\n";
}