Pagini recente » Cod sursa (job #675180) | Borderou de evaluare (job #1342656) | Autentificare | Borderou de evaluare (job #1330683) | Cod sursa (job #1494603)
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <climits>
#define w 100001
#define x first
#define y second
using namespace std;
typedef pair<int,int> ret;
ret p[w];
ret q[50];
float dist(ret a,ret b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
float mind=INT_MAX,mini;
void piv(int st, int dr)
{
if (dr-st<=3)
{
if (dr-st+1==3)
{
mind=min(mind,dist(p[st],p[dr]));
mind=min(mind,dist(p[st+1],p[dr]));
mind=min(mind,dist(p[st],p[st+1]));
}
else
if(dr-st+1==2)
{
mind=min(mind,dist(p[st],p[dr]));
}
}
else
{
int mij=(p[st].x+p[dr].x)/2,i;
for (i=st;i<=dr&&p[i].x<=mij;i++);
piv(st,i-1);piv(i,dr);
}
}
void pic(int st, int dr)
{
if (st<dr)
{
int mij=(p[st].x+p[dr].x)/2,i,sf,j;
for (i=st;i<=dr&&p[i].x<=mij-mini;i++);
sf=0;
for(;i<=dr&&p[i].x<=mij+mini;i++)
{
q[++sf]=p[i];
}
//sort(q+1,q+sf+1);
if (sf<=7)
{
for (i=1;i<sf;i++)
for (j=i+1;j<=sf;j++)
{
mind=min(mind,dist(p[i],p[j]));
}
}
else
{
int y=sf/7,ii;
for (ii=1;ii<=y;ii++)
{
for (i=(ii-1)*7;i<7*ii;i++)
for (j=i+1;j<=7*ii;j++) mind=min(mind,dist(p[i],p[j]));
}
for (i=y*7;i<sf;i++)
for (j=i+1;j<=sf;j++) mind=min(mind,dist(p[i],p[j]));
}
for (i=st;i<=dr&&p[i].x<=mij;i++);
pic(st,i-1);pic(i,dr);
}
}
int main()
{
ifstream f("cmap.in");
ofstream g("cmap.out");
int n,i;
f>>n;
for (i=1;i<=n;i++)
{
f>>p[i].x>>p[i].y;
}
sort(p+1,p+n+1);
piv(1,n);
mini=mind;
pic(1,n);
int m=int(mind),h=0;
while (m!=0)
{
h++;
m/=10;
}
g<<setprecision(h+6)<<mind<<'\n';
f.close();
g.close();
return 0;
}