Cod sursa(job #628171)

Utilizator mlupseLupse-Turpan Mircea mlupse Data 31 octombrie 2011 18:45:15
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iomanip>
#define dist(a1,b1,a2,b2) (a1-a2)*(a1-a2)+(b1-b2)*(b1-b2)

using namespace std;

typedef long long i64;

const int MAX_N = 100005;
const i64 INF = 4000000000000000000LL;

vector < pair <i64, i64> > V(MAX_N), X, Y;

i64 go(int st, int dr, vector < pair <i64, i64> >& X, vector < pair <i64, i64> >& Y) {
    if (st >= dr - 1)
        return INF;
    else if (dr - st == 2) {
        //if (Y[st] > Y[st + 1])
          //  swap(Y[st], Y[st + 1]);
        return dist(X[st].first,X[st].second, X[st + 1].first,X[st + 1].second);
    }
    int mid = (st + dr) / 2;
    i64 best = min(go(st, mid, X, Y), go(mid, dr, X, Y));

    //merge(Y.begin() + st, Y.begin() + mid, Y.begin() + mid, Y.begin() + dr, V.begin());
    //copy(V.begin(), V.begin() + (dr - st), Y.begin() + st);

    int v_size = 0;
    for (int i = st; i < dr; ++ i) if (abs(Y[i].second - X[mid].first) <= best)
        V[v_size ++] = Y[i];
    for (int i = 0; i < v_size - 1; ++ i) {
        for (int j = i + 1; j < v_size && j - i < 8; ++ j)
            best = min(best, dist(V[i].first,V[i].second, V[j].first,V[j].second));
    }
    return best;
}

int main(void) {
    int n;
    ifstream in("cmap.in");
    in >> n; 
    
    
    X.resize(n), Y.resize(n);
    for (int i = 0; i < (int) X.size(); ++ i) 
        in >> X[i].first >> X[i].second;
        
    in.close();
   
    sort(X.begin(), X.end());
    for (int i = 0; i < (int) X.size(); ++ i)
        Y[i] = make_pair(X[i].second, X[i].first);

    ofstream out("cmap.out");
    out << fixed << setprecision(6) << sqrt((float)go(0, (int) X.size(), X, Y)) << "\n";
    out.close();
    return 0;
}