Cod sursa(job #1026275)

Utilizator krissu93FMI Tiugan Cristiana Elena krissu93 Data 11 noiembrie 2013 14:28:02
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.57 kb
#include <fstream>
#include <math.h>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;

const int INF = (1<<30);
const int Nmax = 100000;
int n;
pair<int, int> puncte[Nmax];



void getData(){

    ifstream in("cmap.in");
    in>>n;
    for (int i=0; i<n; ++i){
        int x,y;
        in>>x>>y;
        puncte[i]=pair<int, int>(x,y);
    }

}


bool compAbs(const pair<int, int>& A, const pair<int, int>& B ){

    return (A.first < B.first);
}

bool compOrd(const pair<int, int>& A, const pair<int, int>& B) {

    return (A.second < B.second);
}

long long distanta(const pair<int, int>&A, const pair<int, int>& B){

    long long x = (A.first-B.first)*(A.first-B.first);
    long long y = (A.second-B.second) * (A.second-B.second);
    return x+y;
}

long long divide(const int& st, const int& dr){

    if ( dr - st <=2){
        // sunt pe cazul |p| <=3, caut cea mai apropiata pereche;
        long long dMin = INF;
        for (int i = st; i<dr; ++i){
            for (int j = i+1; j<=dr; ++j){

                long long aux = distanta(puncte[i],puncte[j]);
                dMin = min(dMin, aux);
            }
        }
        //sortam submultimi dupa ordonata
        sort(puncte+st,puncte+dr+1,compOrd);
        return dMin;
    }else {
        int mij  = (st+dr)/2;

        vector< pair<int, int> > sir;

        long long s1 = divide(st,mij);
        long long s2 = divide (mij+1,dr);
        long long dMin = min(s1,s2);

        int i = st, j = mij+1;

        //INTERCLASRE:

        while (i<=mij && j<=dr)
            if( compOrd(puncte[i],puncte[j])==true){
                sir.push_back(puncte[i]);
                ++i;
            }else{
                sir.push_back(puncte[j]);
                ++j;
            }
        while (i<=mij) {

            sir.push_back(puncte[i]);
            ++i;
        }

        while (j<=dr){
            sir.push_back(puncte[j]);
            ++j;
        }

        //Distanta:

        int sirSize = dr-st+1;
        for (i=0; i<sirSize; ++i)
            puncte[i+st] = sir[i];

        sir.clear();
        for(int i=0; i<sirSize; ++i)

            for (int j=i+1; j<sirSize && (j-i)<8;++j){
                long long d = distanta(puncte[i],puncte[j]);
                dMin = min(d,dMin);

            }


        return dMin;
    }
}

int main(){

getData();
sort(puncte, puncte+n, compAbs);
ofstream out("cmap.out");
long long d = divide(0,n-1);
out<<setprecision(10)<<sqrt(d);
return 0;

}