Pagini recente » Cod sursa (job #837437) | Cod sursa (job #1157090) | Cod sursa (job #1878387) | Cod sursa (job #1657323) | Cod sursa (job #1214552)
#include <fstream>
#include <ctime>
#include <cstdlib>
#include <utility>
#include <cmath>
#include <iomanip>
#include <iostream>
#define MAX 100001
double myV[MAX][2];
int myY[MAX];
int aux[MAX];
double dist(int a, int b)
{
return sqrt((myV[b][0] - myV[a][0]) * (myV[b][0] - myV[a][0]) + (myV[b][1] - myV[a][1]) * (myV[b][1] - myV[a][1]));
}
void quickSort(int left, int right)
{
if (left >= right)
{
return;
}
int l = left, r = right;
double pivot = myV[l + rand() % (r - l)][0];
while (l < r)
{
while (myV[l][0] < pivot)
{
l++;
}
while (myV[r][0] > pivot)
{
r--;
}
if (l <= r)
{
std::swap(myV[l], myV[r]);
l++;
r--;
}
}
quickSort(l, right);
quickSort(left, r);
}
double closest(int l, int r)
{
if (l + 1 == r)
{
if (myV[l][1] > myV[r][1])
{
myY[l] = r;
myY[r] = l;
}
return dist(l, r);
}
if (l == r)
{
return LONG_MAX;
}
int m = (l + r) / 2;
double c = std::min(closest(l, m), closest(m + 1, r));
double cenX = myV[m][0];
int lefty = l, righty = m + 1, k = 0;
while (lefty <= m && righty <= r)
{
if (myV[myY[lefty]][1] < myV[myY[righty]][1])
{
aux[k++] = myY[lefty];
lefty++;
}
else
{
aux[k++] = myY[righty];
righty++;
}
}
while (lefty <= m)
{
aux[k++] = myY[lefty];
lefty++;
}
while (righty <= r)
{
aux[k++] = myY[righty];
righty++;
}
int index = l;
for (int i = 0; i < k; i++)
{
myY[index] = aux[i];
index++;
}
k = 0;
for (int i = l; i <= r; i++)
{
if (abs(myV[myY[i]][0] - cenX) <= c)
{
aux[k++] = myY[i];
}
}
for (int i = 0; i < k - 1; i++)
{
for (int j = i + 1; j < std::min(k, i + 8); j++)
{
c = std::min(c, dist(aux[i], aux[j]));
}
}
return c;
}
int main()
{
srand(time(NULL));
std::ifstream in("cmap.in");
std::ofstream out("cmap.out");
int nV;
in >> nV;
for (int i = 0; i < nV; i++)
{
double a, b;
in >> a >> b;
myV[i][0] = a;
myV[i][1] = b;
myY[i] = i;
}
in.close();
quickSort(0, nV - 1);
out << std::fixed << std::setprecision(6) << closest(0, nV - 1) << '\n';
out.close();
return 0;
}