Pagini recente » Cod sursa (job #118505) | Cod sursa (job #2653582) | Cod sursa (job #467132) | Cod sursa (job #383226) | Cod sursa (job #1021542)
#include <iostream>
#include <fstream>
#include <cstdio>
#include <math.h>
#include <vector>
#include <algorithm>
#include <iomanip>
const static int NMAX = 100000;
using namespace std;
class Point2D
{
public:
int x , y;
Point2D(const int & x , const int & y);
Point2D():x(0),y(0){};
bool operator<(const Point2D & other) const;
bool operator>(const Point2D & other) const;
};
Point2D::Point2D(const int & x , const int & y)
{
this->x = x;
this->y = y;
}
double distancePoints(const Point2D & point1 , const Point2D & point2)
{
int dif1 = point2.x - point1.x;
int dif2 = point2.y - point1.y;
return sqrt(dif1 * dif1 + dif2 * dif2);
}
bool Point2D::operator< (const Point2D & other) const
{
if (x < other.x) return true;
else if (x > other.x) return false;
else return (y < other.y);
}
bool Point2D::operator>(const Point2D & other) const
{
if (x > other.x) return true;
else if (x < other.x) return false;
else return (y < other.y);
}
vector<Point2D> points;
int nr_points = 0;
ifstream input("cmap.in");
ofstream output("cmap.out");
double divide_and_conquer(int left , int right)
{
if (right - left <= 3)
{
double min_distance = 10000.0;
for (int i = left;i<=right;i++)
for (int j = left;j<=right;j++)
if (i != j && min_distance > distancePoints(points[i],points[j]))
{
min_distance = distancePoints(points[i],points[j]);
}
return min_distance;
}
else
{
int middle = (left + right) >> 1;
double d1 = divide_and_conquer(left , middle);
double d2 = divide_and_conquer(middle + 1 , right);
double d = min(d1 , d2);
vector<Point2D> v(right - left + 1);
int p = 0;
for (int i = left , p = 0;i<=right;i++,p++)
v[p] = points[i];
for (int i = 0; i < p; ++i)
for (int j = i + 1; j < p && (j - i) < 8; ++j)
d = min(d, distancePoints(v[i], v[j]));
return d;
}
}
int main(int argc , char * argv[])
{
input >> nr_points;
for (int i = 0;i<nr_points;i++)
{
int x , y;
input >> x >> y;
points.push_back(Point2D(x,y));
}
sort(points.begin(),points.end());
output << setprecision(20) << divide_and_conquer(0 , nr_points - 1);
input.close();
output.close();
return 0;
}