Pagini recente » Cod sursa (job #1691953) | Cod sursa (job #2433333) | Cod sursa (job #1743361) | Cod sursa (job #3190879) | Cod sursa (job #1214324)
#include <fstream>
#include <vector>
#include <ctime>
#include <cstdlib>
#include <utility>
#include <cmath>
#include <iomanip>
#include <climits>
struct Point
{
Point(double a, double b)
{
x = a;
y = b;
}
double x, y;
};
double dist(Point a, Point b)
{
return sqrt((b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y));
}
void quickSortX(std::vector<Point> &myV, int left, int right)
{
if (left >= right)
{
return;
}
int l = left;
int r = right;
Point pivot = myV[left + rand() % (right - left)];
while (l < r)
{
while (myV[l].x < pivot.x)
{
l++;
}
while (pivot.x < myV[r].x)
{
r--;
}
if (l <= r)
{
std::swap(myV[l], myV[r]);
l++;
r--;
}
}
quickSortX(myV, left, r);
quickSortX(myV, l, right);
}
void quickSortY(std::vector<Point> &myV, int left, int right)
{
if (left >= right)
{
return;
}
int l = left;
int r = right;
Point pivot = myV[left + rand() % (right - left)];
while (l < r)
{
while (myV[l].y < pivot.y)
{
l++;
}
while (pivot.y < myV[r].y)
{
r--;
}
if (l <= r)
{
std::swap(myV[l], myV[r]);
l++;
r--;
}
}
quickSortY(myV, left, r);
quickSortY(myV, l, right);
}
double bruteForce(std::vector<Point> myX)
{
double d = LONG_MAX;
for (int i = 0; i < (int)myX.size() - 1; i++)
{
for (int j = i + 1; j < (int)myX.size(); j++)
{
d = std::min(d, dist(myX[i], myX[j]));
}
}
return d;
}
double getPair(std::vector<Point> myX, std::vector<Point> myY)
{
if (myX.size() <= 3)
{
return bruteForce(myX);
}
int nSize = (int)myX.size();
int m = nSize / 2;
std::vector<Point> leftX, rightX;
for (int i = 0; i < m; i++)
{
leftX.push_back(myX[i]);
}
for (int i = m; i < nSize; i++)
{
rightX.push_back(myX[i]);
}
Point center = leftX.back();
std::vector<Point> leftY, rightY;
nSize = (int)myY.size();
for (int i = 0; i < nSize; i++)
{
if (center.x > myY[i].x)
{
leftY.push_back(myY[i]);
}
else
{
rightY.push_back(myY[i]);
}
}
double c = std::min(getPair(leftX, leftY), getPair(rightX, rightY));
std::vector<Point> myClose;
for (int i = 0; i < nSize; i++)
{
if (abs(myY[i].x - center.x) < c)
{
myClose.push_back(myY[i]);
}
}
nSize = (int)myClose.size();
for (int i = 0; i < nSize - 1; i++)
{
int index = std::min(nSize, i + 8);
for (int j = i + 1; j < index; j++)
{
c = std::min(c, dist(myClose[i], myClose[j]));
}
}
return c;
}
int main()
{
srand(time(NULL));
std::ifstream in("cmap.in");
std::ofstream out("cmap.out");
int nV;
in >> nV;
std::vector<Point> myX, myY;
for (int i = 0; i < nV; i++)
{
double a, b;
in >> a >> b;
myX.push_back(Point(a, b));
myY.push_back(Point(a, b));
}
in.close();
quickSortX(myX, 0, nV - 1);
quickSortY(myY, 0, nV - 1);
double d = getPair(myX, myY);
out << std::fixed << std::setprecision(6) << d << '\n';
out.close();
return 0;
}