Pagini recente » Cod sursa (job #1722339) | Cod sursa (job #797773) | Cod sursa (job #1120724) | Cod sursa (job #750150) | Cod sursa (job #610316)
Cod sursa(job #610316)
#include <fstream>
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <limits>
#include <cmath>
using namespace std;
struct Point
{
Point()
{}
Point(const int xx, const int yy) : x(xx), y(yy)
{}
int x,y;
};
struct VComp
{
inline const bool operator() (const Point& p1, const Point& p2) const
{
if (p1.y < p2.y)
return true;
else if (p1.y > p2.y)
return false;
if (p1.x < p2.x)
return true;
if (p1.x > p2.x)
return false;
return true;
}
};
struct HComp
{
inline const bool operator() (const Point& p1, const Point& p2) const
{
if (p1.x < p2.x)
return true;
if (p1.x > p2.x)
return false;
if (p1.y < p2.y)
return true;
else if (p1.y > p2.y)
return false;
return true;
}
};
double ClosestPair(vector<Point>& vPoints)
{
int leftMostCandidateIndex=0;
double crtDist = numeric_limits<int>::max();
multiset<Point, VComp> candidates;
for (vector<Point>::iterator it=vPoints.begin(); it!=vPoints.end(); ++it)
{
while (it->x - vPoints[leftMostCandidateIndex].x > crtDist)
{
candidates.erase(vPoints[leftMostCandidateIndex]);
leftMostCandidateIndex++;
}
for (multiset<Point, VComp>::iterator itm=candidates.begin(); itm!=candidates.end(); ++itm)
{
double dist = (it->x - itm->x)*(it->x - itm->x) + (it->y - itm->y)*(it->y - itm->y);
//cout << "Intermediate dist = " << dist << endl;
if (dist < crtDist)
{
crtDist = dist;
}
}
candidates.insert(*it);
}
//cout.precision(40);
//cout << (double)sqrt(crtDist) << endl;
return sqrt(crtDist);
}
int main()
{
int n;
vector<Point> vPoints;
HComp hcomp;
fstream fin("cmap.in", fstream::in);
fstream fout("cmap.out", fstream::out);
fin >> n;
//cout << n << endl;
for (int i=0; i<n; ++i)
{
int x, y;
fin >> x >> y;
vPoints.push_back(Point(x,y));
//cout << vPoints[i].x << " " << vPoints[i].y << endl;
}
cout << endl;
sort(vPoints.begin(), vPoints.end(), hcomp);
/*for (int i=0; i<n; ++i)
{
cout << vPoints[i].x << " " << vPoints[i].y << endl;
}*/
fout.precision(40);
fout << ClosestPair(vPoints);
fin.close();
fout.close();
return 0;
}