Pagini recente » Cod sursa (job #1523643) | Cod sursa (job #2034968) | Cod sursa (job #2182144) | Cod sursa (job #1910051) | Cod sursa (job #545874)
Cod sursa(job #545874)
#include<cstdio>
#include<math.h>
#include<stdlib.h>
struct point{
int x,y;};
typedef struct point Point;
float distance(Point a, Point b)
{
float d;
d = (a.x - b.x) * (a.x - b.x);
d += (a.y - b.y) * (a.y - b.y);
return sqrt(d);
}
int comparePoints(const void * a, const void * b)
{
return ((Point*)a)->x - ((Point*)b)->x;
}
float findLowest(Point * p[],int length)
{
float lowest = 2000000000;
for(int i = 0; i < length;i++)
{
for(int j = i+1;j<=i+7 && j <= length;j++)
{
float d = distance(*p[i],*p[j]);
if(d<lowest)
lowest = d;
}
}
return lowest;
}
float lowestDistance(Point p[],int start, int end)
{
int middle = (start + end)/2;
int middleX = p[middle].x;
float d;
float 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;
}
float d1 = lowestDistance(p,start,middle);
float 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];
float 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);
float d = lowestDistance(points,0,n);
printf("%5.6f\n",d);
}