Pagini recente » Cod sursa (job #1488687) | Cod sursa (job #621037) | Cod sursa (job #2370083) | Cod sursa (job #1189857) | Cod sursa (job #918357)
Cod sursa(job #918357)
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
struct pct
{int x,y;};
pct a[100002],b[100002];
int n;
long long minim=123456789101213;
int ax,ay,bx,by;
bool Sortar(pct c, pct d)
{
if(c.x==d.x) return c.y<d.y;
return c.x<d.x;
}
bool Sortare(pct c, pct d)
{
if(c.y==d.y) return c.x<d.x;
return c.y<d.y;
}
void Citire()
{
int i;
freopen("cmap.in","r",stdin);
scanf("%d",&n);
for(i=1; i<=n; i++)
{
scanf("%d %d",&a[i].x,&a[i].y);
b[i].x=a[i].x; b[i].y=a[i].y;
}
sort(a+1,a+n+1,Sortar);
sort(b+1,b+n+1,Sortare);
// for(i=1; i<=n; i++)
//
// printf("%d %d\n",b[i].x,b[i].y);
}
void DivImp(int p1, int p2)
{
int i,j;
long long x;
if(p2-p1<=3)
{
for(j=p1; j<p2; j++)
for(i=j+1; i<=p2; i++)
{
x=(a[j].x-a[i].x)*(a[j].x-a[i].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y);
if(x<minim) {minim=x; ax=a[i].x; ay=a[i].y; bx=a[j].x; by=a[j].y;}
}
//printf("%d %d\n",p1,p2);
}
else
{
//printf("%d %d=\n",p1,p2);
DivImp(p1,(p1+p2)/2);
DivImp((p1+p2)/2-1,p2);
}
}
void DivImpe(int p1, int p2)
{
int i,j;
long long x;
//printf("%d %d\n",p1,p2);
if(p2-p1<=3)
{
for(j=p1; j<p2; j++)
for(i=j+1; i<=p2; i++)
{
x=(b[j].x-b[i].x)*(b[j].x-b[i].x)+(b[i].y-b[j].y)*(b[i].y-b[j].y);
if(x<minim) {minim=x; ax=b[i].x; ay=b[i].y; bx=b[j].x; by=b[j].y;}
}
}
else
{
//printf("%d %d=\n",p1,p2);
DivImpe(p1,(p1+p2)/2);
DivImpe((p1+p2)/2-1,p2);
}
}
int main()
{
double rez;
Citire();
DivImp(1,n);
DivImpe(1,n);
rez=sqrt(minim);
freopen("cmap.out","w",stdout);
printf("%f",rez);
//Sortar();
return 0;
}