Pagini recente » Cod sursa (job #2661948) | Cod sursa (job #498828) | Cod sursa (job #1155364) | Cod sursa (job #233996) | Cod sursa (job #948503)
Cod sursa(job #948503)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <cmath>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
struct point
{
double x;
double y;
point() { }
point( double _x, double _y ) : x(_x), y(_y) { }
bool operator < ( const point & a ) const {
return x != a.x ? x < a.x : y < a.y;
}
};
struct cmpy
{
bool operator() (const point & a, const point & b) const {
return a.y != b.y ? a.y < b.y : a.x < b.x;
}
};
double get_dist_sqr(const point & a, const point & b)
{
return pow(a.x-b.x, 2) + pow(a.y-b.y, 2);
}
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() );
set<point, cmpy> sorty;
double best = 1e10;
int lox = 0;
for (int i = 0; i < n; ++i) {
while (P[lox].x <= P[i].x - best) { // require best > 0
sorty.erase(P[lox]);
++lox;
}
set<point, cmpy>::iterator lo = sorty.upper_bound( point(P[i].x, P[i].y - best) ); // require best > 0
set<point, cmpy>::iterator hi = sorty.lower_bound( point(P[i].x, P[i].y + best) );
double best_sqr = pow(best, 2);
for (set<point, cmpy>::iterator it = lo; it != hi; ++it) {
best_sqr = min( best_sqr, get_dist_sqr(P[i], *it) );
}
best = sqrt(best_sqr);
sorty.insert(P[i]);
}
fout.precision(15);
fout << fixed << best;
return 0;
}