Pagini recente » Cod sursa (job #2096086) | Cod sursa (job #529227) | Cod sursa (job #2601492) | Cod sursa (job #3200756) | Cod sursa (job #3233300)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>
using namespace std;
struct Point {
int x, y;
};
// Comparators for sorting points
bool compareX(const Point &a, const Point &b) {
return a.x < b.x;
}
bool compareY(const Point &a, const Point &b) {
return a.y < b.y;
}
// Function to calculate the distance between two points
double dist(const Point &p1, const Point &p2) {
return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}
// Function to find the distance between the closest points in a strip
double stripClosest(vector<Point> &strip, double d) {
double minDist = d;
sort(strip.begin(), strip.end(), compareY); // Sort the strip according to the y coordinate
for (size_t i = 0; i < strip.size(); ++i) {
for (size_t j = i + 1; j < strip.size() && (strip[j].y - strip[i].y) < minDist; ++j) {
minDist = min(minDist, dist(strip[i], strip[j]));
}
}
return minDist;
}
// Recursive function to find the smallest distance
double closestUtil(vector<Point> &points, size_t left, size_t right) {
if (right - left <= 3) {
double minDist = numeric_limits<double>::infinity();
for (size_t i = left; i < right; ++i) {
for (size_t j = i + 1; j < right; ++j) {
minDist = min(minDist, dist(points[i], points[j]));
}
}
return minDist;
}
size_t mid = left + (right - left) / 2;
Point midPoint = points[mid];
double dl = closestUtil(points, left, mid);
double dr = closestUtil(points, mid, right);
double d = min(dl, dr);
vector<Point> strip;
for (size_t i = left; i < right; ++i) {
if (abs(points[i].x - midPoint.x) < d) {
strip.push_back(points[i]);
}
}
return min(d, stripClosest(strip, d));
}
// Function to find the smallest distance
double closest(vector<Point> &points) {
sort(points.begin(), points.end(), compareX);
return closestUtil(points, 0, points.size());
}
int main() {
ifstream infile("cmap.in");
ofstream outfile("cmap.out");
int n;
infile >> n;
vector<Point> points(n);
for (int i = 0; i < n; ++i) {
infile >> points[i].x >> points[i].y;
}
double result = closest(points);
outfile.precision(6);
outfile << fixed << result << endl;
infile.close();
outfile.close();
return 0;
}