Pagini recente » Cod sursa (job #3255392) | Cod sursa (job #1233042) | Cod sursa (job #3255647) | Cod sursa (job #3184983) | Cod sursa (job #2489328)
#include <bits/stdc++.h>
using namespace std;
bool cmp_y(pair <double, double> p1, pair <double, double> p2) {
return p1.second < p2.second;
}
double distance(pair <double, double> p1, pair <double, double> p2) {
return sqrt(pow(p1.first - p2.first, 2) + pow(p1.second - p2.second, 2) );
}
double merge(int left, int mid, int right, vector <pair<double, double> > points, double min_dist) {
vector <pair <double, double> > new_points;
for (int i = left; i <= right; i++) {
{
if (points[i].first < points[mid].first + min_dist && points[i].first > points[mid].first - min_dist) {
new_points.push_back(points[i]);
}
}
}
sort(new_points.begin(), new_points.end(), cmp_y);
double dist = min_dist;
for (int i = 0; i < new_points.size(); i++) {
for (int j = 1; j < 9 && (i + j) < new_points.size(); j++) {
dist = min(dist, distance(new_points[i], new_points[i + j]));
}
}
return dist;
}
double divide(int left, int right, vector < pair <double, double> > points) {
if (right - left + 1 <= 3) {
double min_dist = numeric_limits<double>::max();
for (int i = left; i < right; i++) {
for (int j = i + 1; j <= right; j++) {
double curr_dist = distance(points[i], points[j]);
if (curr_dist < min_dist) {
min_dist = curr_dist;
}
}
}
return min_dist;
}
int mid = (left + right) / 2;
double min_dist_left = divide(left, mid, points);
double min_dist_right = divide(mid, right, points);
double min_dist = (min_dist_left < min_dist_right) ? min_dist_left:min_dist_right;
min_dist = min (merge(left, mid, right, points, min_dist), min_dist) ;
return min_dist;
}
int main()
{
ifstream f("cmap.in");
ofstream g("cmpa.out");
int n;
vector< pair<double, double> > points;
f >> n;
for (int i = 0; i < n; i++) {
pair <double, double> read;
f >> read.first >> read.second;
points.push_back(read);
}
sort(points.begin(), points.end());
g << setprecision(6) << divide(0, n, points) << "\n";
return 0;
}