Pagini recente » Cod sursa (job #1011193) | Cod sursa (job #2066597)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
const long long dMax = 1000000;
struct Point{
long long x;
long long y;
};
double returnDist(Point& P1, Point& P2)
{
return sqrt( pow(P2.x - P1.x, 2) + pow(P2.y - P1.y, 2) );
}
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;
double returnDistMin(long left, long right)
{
long i, j;
double dist = dMax;
for(i = left; i < right - 1; i++)
for(j = i + 1 ; j < right; j++)
{
if(returnDist(Points[i],Points[j]) < dist )
dist = returnDist(Points[i],Points[j]);
}
return dist;
}
double divideClosPoints(long left, long right)
{
if(right - left <= 4)
return returnDistMin(left, right);
long middle = (right - left)/2 + left;
double dLeft = divideClosPoints(left, middle);
double dRight = divideClosPoints(middle, right);
double d = min(dLeft, dRight);
long i, j;
vector<Point> verticalSec;
for(i = left ; i < right; i++)
{
if(returnDist(Points[i],Points[middle]) < d)
verticalSec.push_back(Points[i]);
}
sort(verticalSec.begin(),verticalSec.end(),compByY);
long long sizeV = verticalSec.size();
for(i = 0; i < sizeV - 1; i++)
for(j = i + 1; j < i + 7 && j < sizeV ; j++)
{
double 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) << divideClosPoints(0,Points.size() - 1);
}