Cod sursa(job #952637)

Utilizator primulDarie Sergiu primul Data 23 mai 2013 19:12:17
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
#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;
}