Pagini recente » Cod sursa (job #2483350) | Cod sursa (job #75051) | Cod sursa (job #124944) | Mexitate | Cod sursa (job #1385844)
#include <cmath>
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 100005;
const long long inf = 4e18;
struct point {
long long x, y;
};
int N;
point Px[MAXN];
point Py[MAXN];
vector<point> S;
bool cmp1(point a, point b) {
if(a.x == b.x)
return a.y < b.y;
return a.x < b.x;
}
bool cmp2(point a, point b) {
if(a.y == b.y)
return a.x < b.x;
return a.y < b.y;
}
long long dist(point a, point b) {
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
long long split(int st, int dr, long long d) {
S.clear();
int med = (st + dr) / 2;
long long xm = Px[med].x;
long long dmin = d;
for(int i = 1; i <= N; ++i) {
if(Py[i].x >= xm - d && Py[i].x <= xm + d) {
S.push_back(Py[i]);
}
}
for(int i = 0; i < S.size() - 1; ++i) {
for(int j = 1; j <= 7 && i + j < S.size(); ++j) {
long long dc = dist(S[i], S[i + j]);
if(dc < dmin)
dmin = dc;
}
}
return dmin;
}
long long solve(int st, int dr) {
//cout << st << ' ' << dr << '\n';
if(dr - st == 2) {
return min(min(dist(Px[st], Px[st + 1]), dist(Px[st], Px[dr])), dist(Px[st + 1], Px[dr]));
}
if(dr - st == 1) {
return dist(Px[st], Px[dr]);
}
long long d1 = solve(st, (st + dr) / 2);
long long d2 = solve((st + dr) / 2 + 1, dr);
//if(!d1 || !d2)
//cout << st << ' ' << dr << ' ' << d1 << ' ' << d2 <<'\n';
long long d3 = split(st, dr, min(d1, d2));
return d3;
}
int main()
{
ifstream cin("cmap.in");
ofstream cout("cmap.out");
cin >> N;
for(int i = 1; i <= N; ++ i) {
cin >> Px[i].x >> Px[i].y;
Py[i] = Px[i];
}
sort(Px + 1, Px + N + 1, cmp1);
sort(Py + 1, Py + N + 1, cmp2);
cout << fixed << setprecision(6) << sqrt(1.0 * solve(1, N)) << '\n';
return 0;
}