Pagini recente » Cod sursa (job #3291838) | Cod sursa (job #1728492) | Cod sursa (job #1523952) | Cod sursa (job #169812) | Cod sursa (job #1695200)
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#define STRIVE_POINTS 8
using namespace std;
struct Point
{
double x, y;
};
double dist(Point p1, Point p2)
{
return sqrt((p2.x - p1.x) * (p2.x - p1.x) +
(p2.y - p1.y) * (p2.y - p1.y));
}
int compareY(const void *arg1, const void *arg2)
{
Point p1 = *((Point *)arg1);
Point p2 = *((Point *)arg2);
return p2.y - p1.y;
}
int compareX(const void *arg1, const void *arg2)
{
Point p1 = *((Point *)arg1);
Point p2 = *((Point *)arg2);
return p2.x - p1.x;
}
double __getStriveDist(Point *strive, Point midPoint, size_t size, double delta)
{
// here we should also sort the points
qsort(strive, size, sizeof(Point), compareY);
double minDist = delta;
for (int i = 0; i < size; ++i)
{
for (int j = i + 1; j < size
&& (strive[j].y - strive[i].y) < minDist; ++j)
{
minDist = min(strive[j].y - strive[i].y, minDist);
}
}
return minDist;
}
double __getSmallestDist(Point *points, size_t size)
{
if (size <= 3)
{
double d1 = dist(points[0], points[1]);
if (size == 2)
{
return d1;
}
double d2 = dist(points[1], points[2]);
return min(d1, d2);
}
int mid = size / 2;
Point midPoint = points[mid];
double dist1 = __getSmallestDist(points, mid);
double dist2 = __getSmallestDist(points + mid, size - mid);
double delta = min(dist1, dist2);
Point strive[STRIVE_POINTS];
size_t count = 0;
for (int i = 0; i < size; ++i)
{
if (i == mid) continue;
if (dist(points[i], midPoint) < delta)
{
strive[count++] = points[i];
}
}
double dist3 = __getStriveDist(strive, midPoint, count, delta);
return min(dist3, delta);
}
double getSmallestDist(Point *points, size_t size)
{
// here we sort the points
qsort(points, size, sizeof(Point), compareX);
return __getSmallestDist(points, size);
}
Point points[1005];
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
int x, y;
scanf("%d %d", &x, &y);
points[i].x = x;
points[i].y = y;
}
printf("%.6f\n", getSmallestDist(points, n));
return 0;
}