Pagini recente » Cod sursa (job #403568) | Cod sursa (job #983724) | Cod sursa (job #2767229) | Cod sursa (job #1771907) | Cod sursa (job #545878)
Cod sursa(job #545878)
#include<cstdio>
#include<math.h>
#include<stdlib.h>
struct point{
int x,y;};
typedef struct point Point;
double distance(Point a, Point b)
{
double d;
d = pow((double)(a.x - b.x),2.0);
d += pow((double)(a.y - b.y),2.0);
return sqrt(d);
}
int comparePoints(const void * a, const void * b)
{
return ((Point*)a)->x - ((Point*)b)->x;
}
double findLowest(Point * p[],int length)
{
double lowest = 2000000000;
for(int i = 0; i < length;i++)
{
for(int j = i+1;j<=i+7 && j <= length;j++)
{
double d = distance(*p[i],*p[j]);
if(d<lowest)
lowest = d;
}
}
return lowest;
}
double lowestDistance(Point p[],int start, int end)
{
int middle = (start + end)/2;
int middleX = p[middle].x;
double d;
double lowest;
lowest = distance(p[start],p[start+1]);
if(end - start <= 3)
{
for(int i = start; i<end-1;i++)
for(int j = i + 1; j < end;j++)
{
d = distance(p[i],p[j]);
if(d < lowest)
lowest = d;
}
return lowest;
}
double d1 = lowestDistance(p,start,middle);
double d2 = lowestDistance(p,middle, end);
if(d1 < d2)
lowest = d1;
else
lowest = d2;
Point *r[end-start];
int j = -1;
for(int i = start; i < end;i++)
if(abs(middleX-p[i].x) <= lowest)
r[++j] = &p[i];
double lowest2 = findLowest(r,j);
if(lowest2 < lowest)
return lowest2;
return lowest;
}
int main()
{
freopen("cmap.in","r",stdin);
freopen("cmap.out","w",stdout);
int n;
scanf("%d",&n);
Point points[n];
for(int i=0;i<n;i++)
{
int x,y;
scanf("%d %d",&x,&y);
points[i].x = x;
points[i].y = y;
}
qsort(&points,n,sizeof(Point),comparePoints);
double d = lowestDistance(points,0,n);
printf("%5.6f",d);
}