Pagini recente » Cod sursa (job #1531151) | Cod sursa (job #750835) | Istoria paginii utilizator/etohirse | Cod sursa (job #498466) | Cod sursa (job #2969147)
#include <bits/stdc++.h>
using namespace std;
struct point {
int x, y;
bool operator < (const point& other) const {
return ((y < other.y) || (y == other.y && x < other.x));
}
};
const int NMAX = 1e5;
const int INF = 1e9;
point v[NMAX];
static inline long double dist(point a, point b) {
return sqrtl((long long) (a.x - b.x) * (a.x - b.x) + (long long) (a.y - b.y) * (a.y - b.y));
}
bool cmp(point a, point b) {
return ((a.x < b.x) || (a.x == b.x && a.y < b.y));
}
set<point> s;
int main() {
int n;
FILE *fin, *fout;
fin = fopen("cmap.in", "r");
fout = fopen("cmap.out", "w");
fscanf(fin, "%d", &n);
for(int i = 0; i < n; i++) {
fscanf(fin, "%d%d", &v[i].x, &v[i].y);
}
sort(v, v + n, cmp);
/*for(int i = 0; i < n; i++) {
cout << v[i].x << ' ' << v[i].y << endl;
}
cout << endl;*/
long double ans = dist(v[0], v[1]);
s.insert(v[0]);
s.insert(v[1]);
int i = 2;
while(i < n) {
int j = i;
while(j < n && v[j].x == v[i].x) {
auto it1 = s.lower_bound({-INF - 1, v[j].y - (int)ans - 1});
///auto it2 = s.lower_bound({0, v[j].y + (int)ans + 1});
/*cout << s.size() << endl;
cout << j << ": " << endl;
if(it1 != s.end())
cout << (*it1).x << ' ' << (*it1).y << endl; //' ' << (*it2).x << ' ' << (*it2).y << endl;
else {
//cout << i << endl;
}*/
for(auto it = it1; it != s.end() && (*it).y < v[j].y + (int)ans + 1; it++) {
point aux = (*it);
ans = min(ans, dist(v[j], aux));
}
for(auto it = s.begin(); it != s.end();) {
if((*it).x < v[j].x - (int)ans - 1) {
it = s.erase(it);
} else {
it++;
}
}
s.insert(v[j]);
j++;
}
i = j;
}
fprintf(fout, "%.6llf", ans);
fclose(fin);
fclose(fout);
return 0;
}