Pagini recente » Cod sursa (job #3140350) | Cod sursa (job #2894871) | Cod sursa (job #808002) | Cod sursa (job #925909) | Cod sursa (job #2969172)
#include <bits/stdc++.h>
using namespace std;
#define N_MAX 100000
#define INF 2000000000
struct point {
int x, y;
};
bool cmp_x(const point& a, const point& b) {
return a.x < b.x;
}
double dist(const point& a, const point& b) {
return sqrt((double)(a.x - b.x) * (a.x - b.x) + (double)(a.y - b.y) * (a.y - b.y));
}
point v[N_MAX + 1];
struct cmp_y {
bool operator()(const int& a, const int& b) {
return v[a].y < v[b].y;
}
};
int main() {
FILE *fin, *fout;
int n, i;
double min_dist;
fin = fopen("cmap.in", "r");
fscanf(fin, "%d", &n);
for(i = 0; i < n; i++)
fscanf(fin, "%d%d", &v[i].x, &v[i].y);
fclose(fin);
sort(v, v + n, cmp_x);
set<int, cmp_y> s;
s.insert(0);
min_dist = INF;
for(i = 1; i < n; i++) {
for(auto j = s.begin(); j != s.end(); j++) {
if(v[*j].x < v[i].x - min_dist)
j = s.erase(j);
}
v[n] = {-INF, v[i].y - min_dist};
auto it = s.lower_bound(n);
for(;it != s.end() && v[*it].y <= v[i].y + min_dist; it++)
min_dist = min(min_dist, dist(v[i], v[*it]));
s.insert(i);
}
fout = fopen("cmap.out", "w");
fprintf(fout, "%hf", min_dist);
fclose(fout);
return 0;
}