Pagini recente » Cod sursa (job #37490) | Cod sursa (job #2905237) | Cod sursa (job #2698311) | Cod sursa (job #186256) | Cod sursa (job #3236160)
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#define INF 999999999999999999LL
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
int n;
struct point {
long long x, y;
};
vector<point> v;
long long distance(point a, point b) {
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
bool compareX(point a, point b) {
return a.x < b.x || (a.x == b.x && a.y < b.y);
}
bool compareY(point a, point b) {
return a.y < b.y;
}
long long solve(int st, int dr) {
if (st >= dr) {
return INF;
}
if (dr - st == 1) {
return distance(v[st], v[dr]);
}
int mij = (st + dr) / 2;
long long d1 = solve(st, mij);
long long d2 = solve(mij + 1, dr);
long long dmin = min(d1, d2);
vector<point> w;
for (int i = st; i <= dr; ++i) {
if (abs(v[i].x - v[mij].x) * abs(v[i].x - v[mij].x) <= dmin) {
w.push_back(v[i]);
}
}
sort(w.begin(), w.end(), compareY);
for (int i = 0; i < w.size(); ++i) {
for (int j = i + 1; j < w.size() && (w[j].y - w[i].y) * (w[j].y - w[i].y) <= dmin; ++j) {
dmin = min(dmin, distance(w[i], w[j]));
}
}
return dmin;
}
int main() {
fin >> n;
v.resize(n);
for (int i = 0; i < n; ++i) {
fin >> v[i].x >> v[i].y;
}
sort(v.begin(), v.end(), compareX);
long long result = solve(0, n - 1);
fout << setprecision(6) << fixed << sqrt(result);
return 0;
}