Pagini recente » Cod sursa (job #2592234) | Cod sursa (job #2468042) | Cod sursa (job #567245) | Cod sursa (job #800846) | Cod sursa (job #610359)
Cod sursa(job #610359)
#include <fstream>
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <limits>
#include <cmath>
using namespace std;
typedef long long int64;
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 false;
}
};
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;
int64 crtDist = numeric_limits<int64>::max();
multiset<Point, VComp> candidates;
//cout << "Start rocessing\n";
for (vector<Point>::iterator it=vPoints.begin(); it!=vPoints.end(); ++it)
{
//cout << (it->x - vPoints[leftMostCandidateIndex].x) << " " << sqrt(crtDist) << endl;
while (abs(it->x - vPoints[leftMostCandidateIndex].x) > sqrt(crtDist))
{
candidates.erase(vPoints[leftMostCandidateIndex]);
leftMostCandidateIndex++;
//cout << "Erased " << candidates.size() << endl;
}
//cout << "Done\n";
for (multiset<Point, VComp>::iterator itm=candidates.begin(); itm!=candidates.end(); ++itm)
{
int64 dist = (int64)(it->x - itm->x)*(it->x - itm->x) + (int64)(it->y - itm->y)*(it->y - itm->y);
//cout << "Intermediate dist = " << dist << endl;
if (dist < crtDist)
{
crtDist = dist;
}
}
candidates.insert(*it);
/*cout << candidates.size() << endl;
if (candidates.find(*it) == candidates.end())
{
cout <<"Crap\n";
exit(0);
}*/
}
//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(17);
fout << ClosestPair(vPoints) << endl;
fin.close();
fout.close();
return 0;
}