Cod sursa(job #1028531)

Utilizator chimistuFMI Stirb Andrei chimistu Data 14 noiembrie 2013 11:49:40
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <iostream>
#include <fstream>
#define maxn 100001
#include <vector>
#include <algorithm>
#include <math.h>
#include <iomanip>
#define INF 1<<30

using namespace std;

ifstream f("cmap.in");
ofstream g("cmap.out");

vector<pair <int,int> > X,Y,Z(maxn);
int n;

double dist(const pair<int,int> &A, const pair<int,int> &B){
    return sqrt((A.first - B.first)*(A.first - B.first)+(A.second-B.second)*(A.second-B.second));
}

double DivConq(int st, int dr, vector<pair<int,int> > &X, vector<pair<int,int> > &Y){
    if (st>=dr)
        return INFINITY;
    if(st+1 == dr)
        return dist(X[st],X[dr]);
    int mij = (st+dr)/2;
    double rez = min(DivConq(st,mij,X,Y),DivConq(mij+1,dr,X,Y));
    sort(Y.begin()+st,Y.begin()+dr);
    int size_Z=0;
    for(int i = st;i<dr;i++)
        if(abs(Y[i].second - X[mij].first)<=rez)
            Z[size_Z++] = Y[i];
    for(int i=0;i<size_Z -1; ++i){
        for(int j=i+1;j<size_Z && j-i<8; ++j)
            rez = min(rez,dist(Z[i], Z[j]));
    }
    return rez;
}

int main()
{
    f >> n;
    int a,b;
    for(int i=0;i<n;i++){
        f >> a >> b;
        X.push_back(make_pair(a,b));
    }

    sort(X.begin(),X.end());
    for(int i=0;i<X.size();i++){
        Y.push_back(make_pair(X[i].second, X[i].first));
    }
    g << setprecision(8) << DivConq(0,n-1,X,Y);

    return 0;
}