Pagini recente » Cod sursa (job #588963) | Cod sursa (job #329699) | Cod sursa (job #2322671) | Cod sursa (job #605355) | Cod sursa (job #2066677)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
const long long dMax = 10000000000;
struct Point{
long long x;
long long y;
};
long long returnDist(Point& P1, Point& P2)
{
return (P2.x - P1.x) * (P2.x - P1.x) + (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;
double returnDistMin(long left, long right)
{
long i, j;
double dist = dMax;
for(i = left; i < right; i++)
for(j = i + 1 ; j <= right; j++)
{
if( sqrt( returnDist( Points[i],Points[j] ) ) < dist )
dist = sqrt( returnDist(Points[i],Points[j]));
}
return dist;
}
double divideClosPoints(long left, long right)
{
if(right - left < 3)
return returnDistMin(left, right);
long long middle = (right + left)/2;
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( sqrt( 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; i++)
for(j = i + 1; j < i + 7 && j < sizeV ; j++)
{
double distV = sqrt(returnDist(verticalSec[i],verticalSec[j]) );
if(distV < d)
d = distV;
}
return d;
}
double bf()
{
long long i, j;
double dmin = dMax;
cout << "OK\n";
for(i = 0 ; i < Points.size() - 1; i++)
for(j = i + 1; j < Points.size(); j++)
{
if(sqrt(returnDist(Points[i],Points[j])) < dmin)
dmin = sqrt(returnDist(Points[i],Points[j]));
}
return dmin;
}
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);
cout << fixed << setprecision(6) << divideClosPoints(0,Points.size());
}