Pagini recente » Cod sursa (job #1992690) | Cod sursa (job #1562002) | Monitorul de evaluare | Cod sursa (job #1691785) | Cod sursa (job #2070515)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <cmath>
using namespace std;
const double INF = 4e18;
vector<pair<long long, long long> > Points;
vector<pair<long long, long long> > PointsOY;
long long returnDist(pair<long long, long long>& P1,pair<long long, long long>& P2)
{
return (P2.first - P1.first) * (P2.first - P1.first) +
(P2.second - P1.second) * (P2.second - P1.second);
}
long long divideClosPoints(long long left, long long right)
{
if( left >= right -1)
return INF;
else if(right - left == 2)
{
if(PointsOY[left].second > PointsOY[left + 1].second)
swap(PointsOY[left],PointsOY[left + 1]);
return returnDist(Points[left], Points[left + 1]);
}
long long middle = (left + right) / 2;
long long dLeft = divideClosPoints(left, middle);
long long dRight = divideClosPoints(middle, right);
long long d = min(dLeft, dRight);
long i, j;
vector< pair<long long, long long> > sol;
merge(PointsOY.begin() + left, PointsOY.begin() + middle, PointsOY.begin() + middle, PointsOY.begin() + right, sol.begin());
copy(sol.begin(), sol.begin() + (right - left), PointsOY.begin() + left);
int k = 0;
for(i = left; i < right; ++i)
{
if(abs(PointsOY[i].first - Points[middle].first) <= d)
sol[k++] = PointsOY[i];
}
for(i = 0; i < k - 1 ; ++i)
for(j = i + 1; j - i < 8 && j < k ; ++j)
{
d = min(d, returnDist(sol[i],sol[j]));
}
return d;
}
int main()
{
ifstream fileRead("cmap.in");
ofstream fileWrite("cmap.out");
long long nrPoints, i;
long long x, y;
fileRead >> nrPoints;
for(i = 0 ; i < nrPoints; i++)
{
fileRead >> x >> y;
Points.push_back(make_pair(x,y));
PointsOY.push_back(make_pair(x,y));
}
sort(Points.begin(),Points.end());
fileWrite << fixed << setprecision(6) << sqrt(divideClosPoints(0,nrPoints - 1));
fileRead.close();
fileWrite.close();
}