Pagini recente » Cod sursa (job #2094074) | Cod sursa (job #2200741) | Cod sursa (job #2806622) | Cod sursa (job #770827) | Cod sursa (job #3349528)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
struct Point {
long long x, y;
};
bool cmpX(const Point& a, const Point& b) {
if (a.x != b.x) return a.x < b.x;
return a.y < b.y;
}
bool cmpY(const Point& a, const Point& b) {
if (a.y != b.y) return a.y < b.y;
return a.x < b.x;
}
long long dist2(const Point& a, const Point& b) {
long long dx = a.x - b.x;
long long dy = a.y - b.y;
return dx * dx + dy * dy;
}
long long divideEtImpera(vector<Point>& p, int st, int dr) {
if (dr - st <= 3) {
long long ans = (1LL << 62);
for (int i = st; i <= dr; i++) {
for (int j = i + 1; j <= dr; j++) {
ans = min(ans, dist2(p[i], p[j]));
}
}
sort(p.begin() + st, p.begin() + dr + 1, cmpY);
return ans;
}
int mid = (st + dr) / 2;
long long xMid = p[mid].x;
long long dSt = divideEtImpera(p, st, mid);
long long dDr = divideEtImpera(p, mid + 1, dr);
long long d = min(dSt, dDr);
vector<Point> interclasat;
interclasat.reserve(dr - st + 1);
int i = st, j = mid + 1;
while (i <= mid && j <= dr) {
if (cmpY(p[i], p[j])) {
interclasat.push_back(p[i]);
i++;
} else {
interclasat.push_back(p[j]);
j++;
}
}
while (i <= mid) {
interclasat.push_back(p[i]);
i++;
}
while (j <= dr) {
interclasat.push_back(p[j]);
j++;
}
for (int k = 0; k < (int)interclasat.size(); k++) {
p[st + k] = interclasat[k];
}
vector<Point> banda;
for (int k = st; k <= dr; k++) {
long long dx = p[k].x - xMid;
if (dx * dx <= d) {
banda.push_back(p[k]);
}
}
for (int i = 0; i < (int)banda.size(); i++) {
for (int j = i + 1; j < (int)banda.size() && j <= i + 7; j++) {
d = min(d, dist2(banda[i], banda[j]));
}
}
return d;
}
int main() {
int n;
fin >> n;
vector<Point> p(n);
for (int i = 0; i < n; i++) {
fin >> p[i].x >> p[i].y;
}
sort(p.begin(), p.end(), cmpX);
long long ans2 = divideEtImpera(p, 0, n - 1);
long double ans = sqrt((long double)ans2);
fout << fixed << setprecision(6) << (double)ans << '\n';
return 0;
}