Pagini recente » Cod sursa (job #61292) | Cod sursa (job #3190708) | Cod sursa (job #134569) | Cod sursa (job #2055547) | Cod sursa (job #2521957)
#include <stdio.h>
#include <algorithm>
#define INF 0xffffff
using namespace std;
FILE* in = fopen ("cmap.in", "r");
FILE* out = fopen ("cmap.out", "w");
struct Point {int x, y;} arrx[100], arry[100];
int cmpx(const void* a, const void* b)
{
Point *p1 = (Point *)a, *p2 = (Point *)b;
return (p1->x - p2->x);
}
int cmpy(const void* a, const void* b)
{
Point *p1 = (Point *)a, *p2 = (Point *)b;
return (p1->y - p2->y);
}
double dst(Point p1, Point p2)
{
return sqrt((p1.x - p2.x)*(p1.x - p2.x)
+(p1.y - p2.y)*(p1.y - p2.y));
}
double rec (int st, int dr)
{
if (dr - st < 1) {return INF;} // max one point => dist inf
if (dr == st + 1) {return dst(arrx[st], arrx[dr]);} // 2 point => min dst = dst of p1 and p2
if (dr == st + 2) {return min ( dst(arrx[st], arrx[dr]), min (dst(arrx[st], arrx[st+1]), dst(arrx[dr-1], arrx[dr])));}
int m = st + (dr - st) / 2, nr = 0;
double d = min (rec(st, m), rec(m+1, dr)), dd;
dd = d;
Point mid[dr];
for (int i = st; i <= dr; ++i)
{
if (dst(arrx[m], arrx[i]) < d)
{
mid[nr++] = arrx[i];
}
}
qsort (mid, nr, sizeof(Point), cmpy);
for (int i = 0; i < nr-1; ++i)
{
for (int j = i+1; j < nr && (mid[j].y - mid[i].y) < dd; ++j)
{
if (dst (mid[i], mid[j]) < dd)
{
dd = dst (mid[i], mid[j]);
}
}
}
return d;
}
int main(void)
{
int n;
fscanf (in, "%d", &n);
for (int i = 0; i < n; ++i)
{
fscanf (in, "%d%d", &arrx[i].x, &arrx[i].y);
}
fclose (in);
qsort (arrx, n, sizeof(Point), cmpx);
fprintf (out, "%.6f", rec(0, n-1));
fclose (out);
return 0;
}