Pagini recente » Cod sursa (job #377483) | Cod sursa (job #338403) | Cod sursa (job #1458711) | Cod sursa (job #417539) | Cod sursa (job #3154851)
#include <bits/stdc++.h>
using namespace std;
struct Point {
double x, y;
Point() : x(), y() {}
Point(double x, double y) : x(x), y(y) {}
};
using PointPair = pair<Point, Point>;
const PointPair INF = { Point(-1e9, 1e9), Point(1e9, 1e9) };
double dist(const PointPair &points) {
const double d1 = points.second.x - points.first.x;
const double d2 = points.second.y - points.first.y;
return sqrt(d1 * d1 + d2 * d2);
}
PointPair closest_pair_two(const PointPair &pair1, const PointPair &pair2) {
return dist(pair1) < dist(pair2) ? pair1 : pair2;
}
PointPair strip_closest_pair(const vector<Point> &points) {
PointPair ans = { points[0], points[1] };
for (int i = 0; i < (int)points.size(); ++i)
for (int j = i + 1; j < (int)points.size() && j - i < 9; ++j)
ans = closest_pair_two(ans, { points[i], points[j] });
return ans;
}
PointPair divide_and_conquer(const vector<Point> &points, int l, int r) {
if (l == r) return INF;
const int mid = (l + r) >> 1;
PointPair ans_left = divide_and_conquer(points, l, mid);
PointPair ans_right = divide_and_conquer(points, mid + 1, r);
PointPair ans = closest_pair_two(ans_left, ans_right);
const double delta = dist(ans);
vector<Point> strip;
for (int i = l; i < r; ++i)
if (abs(points[i].x - points[mid].x) <= delta)
strip.push_back(points[i]);
sort(strip.begin(), strip.end(), [](Point P1, Point P2) {
return P1.y < P2.y || (P1.x == P2.x && P1.y < P2.y);
});
return closest_pair_two(ans, strip_closest_pair(strip));
}
PointPair closest_pair(vector<Point> &points) {
sort(points.begin(), points.end(), [](Point P1, Point P2) {
return P1.x < P2.x || (P1.x == P2.x && P1.y < P2.y);
});
return divide_and_conquer(points, 0, points.size());
}
int main() {
ifstream fin("cmap.in");
ofstream fout("cmap.out");
int N;
fin >> N;
vector<Point> points(N);
for (Point &point : points)
fin >> point.x >> point.y;
fout << fixed << setprecision(6) << dist(closest_pair(points));
fin.close();
fout.close();
return 0;
}