Pagini recente » Cod sursa (job #2536415) | Cod sursa (job #2840111) | Cod sursa (job #1241011) | Istoria paginii runda/round_2 | Cod sursa (job #2304721)
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <math.h>
using namespace std;
int n;
struct Point
{
int x;
int y;
};
bool sort_x(const Point& left, const Point& right)
{
return left.x < right.x;
}
bool sort_y(const Point& left, const Point& right)
{
return left.y < right.y;
}
long double dist(const Point& left, const Point& right)
{
const long diffX = left.x - right.x;
const long diffY = left.y - right.y;
return diffX * diffX + diffY * diffY;
}
long double dist_min(const vector<Point>& points, int left, int right)
{
if (right - left == 1)
{
return dist(points[left], points[right]);
}
if (right - left == 2)
{
return min(dist(points[left], points[left + 1]),
min(dist(points[left + 1], points[right]), dist(points[left], points[right])));
}
const int mid = (left + right) / 2;
const double dist1 = dist_min(points, left, mid);
const double dist2 = dist_min(points, mid + 1, right);
long double minDist = min(dist1, dist2);
long double delta = sqrt(minDist);
vector<Point> band;
for (int i = left; i <= right; ++i)
{
if ((points[i].x - points[mid].x) <= delta)
{
band.push_back(points[i]);
}
}
inplace_merge(band.begin(), band.begin() + (n / 2), band.end(), sort_y);
for (int i = 0; i < band.size(); ++i)
{
for (int j = i + 1; j <= (i + 7) && j < band.size(); ++j)
{
minDist = min(minDist, dist(band[i], band[j]));
}
}
return minDist;
}
int main()
{
vector<Point> points;
Point aux;
ifstream fin ("cmap.in");
ofstream fout("cmap.out");
fin >> n;
for (int i = 0; i<n; i++)
{
fin >> aux.x >> aux.y;
points.push_back(aux);
}
sort(points.begin(), points.end(), sort_x);
fout << sqrt(dist_min(points, 0, points.size() - 1)) << endl;
}