Pagini recente » Cod sursa (job #979774) | Cod sursa (job #2186523) | Cod sursa (job #2775907) | Cod sursa (job #1621191) | Cod sursa (job #2082817)
#include<fstream>
#include<vector>
#include<algorithm>
#include<float.h>
#include<cmath>
#include <iomanip>
using namespace std;
struct point
{
int x, y;
};
vector<point> xOrderedPoints, yOrderedPoints;
bool abscissaCompare(point a, point b)
{
if(a.x!=b.x)
return a.x < b.x;
else
return a.y < b.y;
}
bool ordinateCompare(point a, point b)
{
if (a.y != b.y)
return a.y < b.y;
else
return a.x < b.x;
}
bool ordinateSmallerOrEqual(point a, point b)
{
return a.y <= b.y;
}
double computeDistance(point a, point b)
{
return sqrt(pow((a.x - b.x), 2) + pow((a.y - b.y), 2));
}
void read()
{
ifstream in("cmap.in");
int n;
point temp;
in >> n;
for (int i = 0; i < n; ++i)
{
in >> temp.x >> temp.y;
xOrderedPoints.push_back(temp);
}
sort(xOrderedPoints.begin(), xOrderedPoints.end(), abscissaCompare);
yOrderedPoints = xOrderedPoints;
}
/*
void merge(vector<point> &points, int left, int middle, int right)
{
vector<point> aux;
aux.resize(right - left + 1);
merge(points.begin() + left, points.begin() + middle, points.begin() + middle+1, points.begin() + right, aux.begin(), ordinateCompare);
copy(aux.begin(), aux.end(), points.begin() + left);
}
*/
void merge(vector<point> &points, int left, int middle, int right)
{
vector<point> leftPoints(points.begin()+left, points.begin() + middle+1);
vector<point> rightPoints(points.begin()+middle+1, points.begin()+right+1);
vector<point>::iterator i=leftPoints.begin(), j=rightPoints.begin(), k=points.begin()+left;
while (i != leftPoints.end() && j != rightPoints.end())
{
if (ordinateSmallerOrEqual(*i, *j))
{
*k = *i;
++i;
}
else
{
*k = *j;
++j;
}
++k;
}
while(i!= leftPoints.end())
{
*k = *i;
++i;
++k;
}
while (j != rightPoints.end())
{
*k = *j;
++j;
++k;
}
}
double divideEtImpera(int left, int right)
{
double minDistance = DBL_MAX;
if (right-left+1 < 4)
{
double tempDistance;
sort(yOrderedPoints.begin()+left, yOrderedPoints.begin()+right+1, ordinateCompare);
for(vector<point>::iterator i=xOrderedPoints.begin() + left; i!=xOrderedPoints.begin() + right; ++i)
for (vector<point>::iterator j = i+1; j != xOrderedPoints.begin() + right +1 ; ++j)
{
tempDistance = computeDistance(*i, *j);
minDistance = min(minDistance, tempDistance);
}
}
else
{
double leftMinDistance, rightMinDistance;
int middle = (left + right) / 2;
leftMinDistance = divideEtImpera(left, middle);
rightMinDistance = divideEtImpera(middle + 1, right);
minDistance = min(leftMinDistance, rightMinDistance);
merge(yOrderedPoints, left, middle, right);
vector<point> yBand;
for (vector<point>::iterator i = yOrderedPoints.begin() + left; i != yOrderedPoints.begin() + right + 1; ++i)
{
if(i->x != xOrderedPoints[middle].x || i->y != xOrderedPoints[middle].y)
if (abs(i->x - xOrderedPoints[middle].x) <= minDistance)
yBand.push_back(*i);
}
for (vector<point>::iterator i = yBand.begin(); i != yBand.end() - 1; ++i)
{
int count = 0;
for (vector<point>::iterator j =i+1; count < 7 && j!=yBand.end(); ++j, ++count)
{
minDistance = min(minDistance, computeDistance(*i, *j));
}
count = 0;
}
}
return minDistance;
}
void print(double distance)
{
ofstream out("cmap.out");
out << fixed << setprecision(6) << distance;
}
int main()
{
read();
print(divideEtImpera(0, xOrderedPoints.size()-1));
return 0;
}