Cod sursa(job #631110)

Utilizator floringh06Florin Ghesu floringh06 Data 7 noiembrie 2011 00:08:41
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.32 kb
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cfloat>
#include <numeric>

using namespace std;

const int    oo  = 0x3f3f3f3f;
const double eps = 1e-9;

typedef long long ll;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;

#define sz(c) int ((c).size())
#define all(c) (c).begin(), (c).end()
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORD(i, a, b) for (int i = (b) - 1; i >= (a); --i)
#define FORIT(i, c) for (__typeof__((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define mp make_pair
#define pb push_back

struct Point {
   ll x, y;
   Point (ll x = 0, ll y = 0) : x(x), y(y) {}
};

double distPointPoint(Point p0, Point p1) {
    double dx = p0.x - p1.x;
    double dy = p0.y - p1.y;   
    
    return sqrt(dx*dx + dy*dy);
}

double closest_pair(vector<Point> &pts) {
    vector<pair<double, int> > sorted;
    FOR(i, 0, sz(pts)) sorted.push_back(make_pair(pts[i].x, i));
    sort(all(sorted));
    pair<pii, double> res = make_pair(pii(-1, -1), DBL_MAX);
    set<pair<double, int> > active;
    int pos = 0;
    FOR(i, 0, sz(sorted)) {
        double x = sorted[i].first, y = pts[sorted[i].second].y;
        while (pos < i && sorted[pos].first < x - res.second) {
            active.erase(make_pair(pts[sorted[pos].second].y, sorted[pos].second));
            pos++;
        }
        set<pair<double, int> >::iterator it = active.lower_bound(make_pair(y - res.second, 0));
        while (it != active.end() && it->first <= y + res.second) {
            double d = distPointPoint(pts[it->second], pts[sorted[i].second]);
            if (d < res.second) {
                res = make_pair(pii(it->second, sorted[i].second), d);
            }
            it++;
        }
        active.insert(make_pair(y, sorted[i].second));
    }
    return res.second;
}

int main () {
    freopen ("cmap.in", "r", stdin);
    freopen ("cmap.out", "w", stdout);
    
    int N;
    scanf ("%d", &N);
    
    vector<Point> pnts(N);
    FOR (i, 0, N) scanf ("%d %d", &pnts[i].x, &pnts[i].y);
    
    printf ("%.9lf\n", closest_pair(pnts));
    
    return 0;
}