Pagini recente » Istoria paginii runda/ioit/clasament | Cod sursa (job #40574) | Cod sursa (job #475238) | Istoria paginii runda/concurs_9_17/clasament | Cod sursa (job #1541319)
#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 long long euclidianDistance (pair <int, int> point1, pair <int, int> point2) {
return (point1.x - point2.x) * 1LL * (point1.x - point2.x) + (point1.y - point2.y) * 1LL * (point1.y - point2.y);
}
template <typename TYPE>
inline TYPE abs (TYPE X) {
return X > 0 ? X : -X;
}
inline long long getDistance (int left, int right) {
if (left != right) {
int middle = left + (right - left) / 2;
int distance = Points[middle].x;
long long distance1 = getDistance (left, middle);
long long distance2 = getDistance (middle + 1, right);
long long distance3 = min (distance1, distance2);
int index1 = left, index2 = middle + 1;
int nrPoints2 = 0;
while (index1 <= middle || index2 <= right) {
if (index2 > right ) Points2[++nrPoints2] = Points[index1++]; else
if (index1 > middle) Points2[++nrPoints2] = Points[index2++]; else
if (Points[index1].y <= Points[index2].y)
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 <= nrPoints2; index2 ++)
distance3 = min (distance3, euclidianDistance (Points2[index1], Points2[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 ("%.7f\n", sqrt(getDistance(1, nrPoints)));
return 0;
}