Pagini recente » Cod sursa (job #640360) | Borderou de evaluare (job #1093164) | Diferente pentru problema/cbinteractiv intre reviziile 7 si 6 | Borderou de evaluare (job #2655590) | Cod sursa (job #3342655)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#define NMax 100005
#define inf 2e9
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
struct punct
{
int x,y;
} p[NMax],y[NMax];
int n;
bool cresc(punct a,punct b)
{
if(a.x<b.x)
return 1;
else if(a.x==b.x)
{
if(a.y<b.y)
return 1;
}
return 0;
}
double rez(int st, int dr)
{
double mn=inf;
int mij=(st+dr)/2;
if(dr-st+1<=3)
{
for(int i=st; i<dr; i++)
{
for(int j=i+1; j<=dr; j++)
{
int dx=p[i].x-p[j].x;
int dy=p[i].y-p[j].y;
mn=min(mn,sqrt(dx*dx+dy*dy));
}
}
return mn;
}
else
{
mn=min(rez(st,mij),rez(mij+1,dr));
}
int cnt=0,i=st,j=mij+1;
while(i<=mij && j<=dr)
{
if(p[i].y<p[j].y)
{
y[++cnt]=p[i];
i++;
}
else
{
y[++cnt]=p[j];
j++;
}
}
while(i<=mij)
{
y[++cnt]=p[i];
i++;
}
while(j<=dr)
{
y[++cnt]=p[j];
j++;
}
for(int i=1; i<=cnt; i++)
{
p[st+i-1]=y[i];
}
for(int i=st; i<=dr; i++)
{
for(int j=i+1; j<=i+7 && j<=dr; j++)
{
if(abs(p[i].x-p[mij].x)<=mn)
{
int dx=p[i].x-p[j].x;
int dy=p[i].y-p[j].y;
mn=min(mn,sqrt(dx*dx+dy*dy));
}
}
}
return mn;
}
int main()
{
fin>>n;
for(int i=1; i<=n; i++)
{
fin>>p[i].x>>p[i].y;
}
sort(p+1,p+n+1,cresc);
fout<<fixed<< setprecision(6)<<rez(1,n);
return 0;
}