Pagini recente » Cod sursa (job #2983477) | Cod sursa (job #1167359)
#include <cmath>
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<double, double> Point;
const double oo = 1e15;
vector<Point> Points;
double Answer;
class CompareY {
public:
bool operator()(const Point &a, const Point &b) const {
if (a.y != b.y)
return a.y < b.y;
return a.x < b.x;
}
};
inline double Distance(const Point &a, const Point &b) {
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
double Solve(vector<Point> &points, const int from, const int to) {
if (from + 1 >= to)
return oo;
if (from + 2 == to) {
if (points[from].y > Points[to - 1].y)
swap(points[from], points[to - 1]);
return Distance(points[from], points[to]);
}
int middle = (from + to) / 2;
double xAxis = points[middle].x;
double minDistance = min(Solve(points, from, middle), Solve(points, middle, to));
vector<Point> aux = vector<Point>(to - from);
merge(points.begin() + from, points.begin() + middle, points.begin() + middle, points.begin() + to, aux.begin(), CompareY());
for (int i = 0; i < to - from; ++i)
points[from + i] = aux[i];
vector<Point> current;
for (int i = from; i < to; ++i)
if (abs(xAxis - points[i].x) < minDistance)
current.push_back(points[i]);
for (int i = 0; i < int(current.size()); ++i)
for (int j = i + 1; j < int(current.size()) && j - i < 8; ++j)
minDistance = min(minDistance, Distance(current[i], current[j]));
return minDistance;
}
void Solve() {
sort(Points.begin(), Points.end());
Answer = Solve(Points, 0, int(Points.size()));
}
void Read() {
ifstream cin("cmap.in");
int n;
cin >> n;
Points = vector<Point>(n);
for (int i = 0; i < n; ++i)
cin >> Points[i].x >> Points[i].y;
cin.close();
}
void Print() {
ofstream cout("cmap.out");
cout << fixed << setprecision(8) << Answer << "\n";
cout.close();
}
int main() {
Read();
Solve();
Print();
return 0;
}