Pagini recente » Cod sursa (job #1658039) | oni-2009-x | Istoria paginii fmi-no-stress-4/solutii/beri | Cod sursa (job #2335646) | Cod sursa (job #2066720)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
struct Point{
long long x;
long long y;
};
long long returnDist(Point& P1, Point& P2)
{
return (long long) (P2.x - P1.x) * (P2.x - P1.x) +
(long long) (P2.y - P1.y) * (P2.y - P1.y);
}
int compByX(const Point& P1,const Point& P2)
{
return P1.x < P2.x;
}
int compByY(const Point& P1,const Point& P2)
{
return P1.y < P2.y;
}
vector<Point> Points;
long long divideClosPoints(long left, long right)
{
if(right - left == 1)
return returnDist(Points[left], Points[right]);
if(right - left == 2)
return min(returnDist(Points[left], Points[left+1]),
min(returnDist(Points[left+1], Points[right]),
returnDist(Points[left], Points[right])));
long middle = (right - left)/2 + left;
long long dLeft = divideClosPoints(left,middle);
long long dRight = divideClosPoints(middle + 1, right);
long long d = min(dLeft, dRight);
long i, j;
vector<Point> verticalSec;
auto delta = ceil( sqrt(d) );
for(i = left ; i <= right; i++)
{
if(abs(Points[i].x - Points[middle].x) <= delta)
verticalSec.push_back(Points[i]);
}
sort(verticalSec.begin(),verticalSec.end(),compByY);
long long sizeV = verticalSec.size();
for(i = 0; i < sizeV ; i++)
for(j = i + 1; j <= i + 7 && j < sizeV ; j++)
{
long long distV = returnDist(verticalSec[i],verticalSec[j]);
if(distV < d)
d = distV;
}
return d;
}
int main()
{
ifstream fileRead("cmap.in");
ofstream fileWrite("cmap.out");
long long nrPoints, i;
Point P;
fileRead >> nrPoints;
for(i = 0 ; i < nrPoints; i++)
{
fileRead >> P.x >> P.y;
Points.push_back(P);
}
sort(Points.begin(),Points.end(),compByX);
fileWrite << fixed << setprecision(6) << sqrt(divideClosPoints(0,Points.size() - 1));
}