Pagini recente » Cod sursa (job #1260012) | Cod sursa (job #2123150) | Cod sursa (job #889200) | Cod sursa (job #44232) | Cod sursa (job #2488237)
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iomanip>
using namespace std;
const int INF = 0x3f3f3f3f;
vector<pair<long long, long long>> points;
void read() {
ifstream fin("cmap.in");
long long n;
fin >> n;
for (int i = 0; i < n; ++i) {
long long x, y;
fin >> x >> y;
points.emplace_back(make_pair(x, y));
}
fin.close();
}
struct cmp {
bool operator()(const pair<long long, long long> &A, const pair<long long, long long> &B) {
return A.first < B.first;
}
};
double dist(const pair<long long, long long> &A, const pair<long long, long long> &B) {
return sqrt((A.first - B.first) * (A.first - B.first) + (A.second - B.second) * (A.second - B.second));
}
void merge(int left_idx, int mid_idx, int right_idx) {
int i = left_idx;
int j = mid_idx;
vector<pair<long long, long long>> temp;
while (i < mid_idx && j < right_idx)
if (points[i].first < points[j].first)
temp.push_back(points[i++]);
else
temp.push_back(points[j++]);
while (i < mid_idx)
temp.push_back(points[i++]);
while (j < right_idx)
temp.push_back(points[j++]);
for (int idx = 0; idx < (int)temp.size(); ++idx)
points[left_idx + idx] = temp[idx];
}
double closest_points(int left_idx, int right_idx) {
if (left_idx >= right_idx)
return INF;
if (left_idx - right_idx == 1) {
merge(left_idx, left_idx, right_idx);
return dist(points[left_idx], points[right_idx]);
}
int mid_index = left_idx + (right_idx - left_idx) / 2;
double mid_value = points[mid_index].first;
double current_best = min(closest_points(left_idx, mid_index), closest_points(mid_index + 1, right_idx));
merge(left_idx, mid_index, right_idx);
vector<pair<long long, long long>> temp;
for (int i = left_idx; i < right_idx; ++i)
if (abs(points[i].first - mid_value) <= current_best)
temp.push_back(points[i]);
for (int i = 0; i < (int)temp.size(); ++i)
for (int j = i + 1; j < temp.size() && j - i < 8; ++j)
current_best = min(current_best, dist(temp[i], temp[j]));
return current_best;
}
void print() {
ofstream fout("cmap.out");
fout << fixed << setprecision(6) << closest_points(0, points.size());
fout.close();
}
int main() {
read();
sort(points.begin(), points.end(), cmp());
print();
return 0;
}