Pagini recente » Cod sursa (job #2685495) | Cod sursa (job #2738874) | Cod sursa (job #636142) | Cod sursa (job #1887223) | Cod sursa (job #1022022)
#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(const Point2D & other);
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;
}
Point2D::Point2D(const Point2D & other)
{
x = other.x;
y = other.y;
}
double distancePoints(const Point2D & point1 , const Point2D & point2)
{
return sqrt(1LL *(point2.x - point1.x) * (point2.x - point1.x) + 1LL * (point2.y - point1.y) * (point2.y - point1.y));
}
bool Point2D::operator< (const Point2D & other) const
{
return x < other.x;
}
bool Point2D::operator>(const Point2D & other) const
{
return x > other.x;
}
vector<Point2D> points , aux_points;
int nr_points = 0;
ifstream input("cmap.in");
ofstream output("cmap.out");
bool cmp(const Point2D & p1 , const Point2D & p2)
{
return p1.y < p2.y;
}
double divide_and_conquer(int left , int right)
{
if (right <= left)
{
return (1 << 30);
}
if (right - left == 1)
{
return distancePoints(points[left],points[right]);
}
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);
aux_points.clear();
for (int i = left; i<=middle && points[middle].x - points[i].x <= d; i++)
aux_points.push_back(points[i]);
for (int i = middle + 1; i<=right && points[i].x - points[middle].x <= d; i++)
aux_points.push_back(points[i]);
sort(aux_points.begin() , aux_points.end() , cmp);
int size = aux_points.size();
for (int i = 0; i < size; ++i)
for (int j = i + 1; j < size && (j - i) < 8; ++j)
d = min(d, distancePoints(aux_points[i], aux_points[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;
}