Pagini recente » Cod sursa (job #1269176) | Cod sursa (job #2253652) | Profil DianaPopa | Cod sursa (job #67036) | Cod sursa (job #1540914)
#include <cstdio>
#include <cmath>
#include <algorithm>
#define x first
#define y second
using namespace std;
const int DIM = 100010;
const double INF = 1000000000;
pair <int, int> Points[DIM], Points2[DIM]; int nrPoints;
inline double euclidianDistance (pair <int, int> point1, pair <int, int> point2) {
return sqrt ((point1.x - point2.x) * 1LL * (point1.x - point2.x) + (point1.y - point2.y) * 1LL * (point1.y - point2.y));
}
inline double getDistance (int left, int right) {
if (left != right) {
int middle = left + (right - left) / 2;
int distance = Points[middle].x;
double distance1 = getDistance (left, middle);
double distance2 = getDistance (middle + 1, right);
double distance3 = min (distance1, distance2);
int index1 = left, index2 = middle + 1;
int nrPoints2 = 0;
while (index1 <= middle || index2 <= right) {
if (Points[index1].y <= Points[index2].y && index1 <= middle)
Points2[++nrPoints2] = Points[index1++];
else
Points2[++nrPoints2] = Points[index2++];
}
for (int index = left; index <= right; index ++)
Points[index] = Points2[index - left + 1];
nrPoints2 = 0;
for (int index = left; index <= right; index ++)
if (abs (Points[index].x - distance) <= distance3)
Points2[++nrPoints2] = Points[index];
for (int index1 = 1; index1 <= nrPoints2; index1 ++)
for (int index2 = index1 + 1; index2 <= index1 + 7; index2 ++)
distance3 = min (distance3, euclidianDistance (Points[index1], Points[index2]));
return distance3;
} else
return INF;
}
int main () {
freopen ("cmap.in" ,"r", stdin );
freopen ("cmap.out","w", stdout);
scanf ("%d", &nrPoints);
for (int i = 1; i <= nrPoints; i ++)
scanf ("%d %d", &Points[i].x, Points[i].y);
sort (Points + 1, Points + nrPoints + 1);
printf ("%.6f\n", getDistance(1, nrPoints));
return 0;
}