Cod sursa(job #1046622)

Utilizator chimistuFMI Stirb Andrei chimistu Data 3 decembrie 2013 11:14:57
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 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;
int n;

bool dupay(pair<int,int> Q, pair<int,int>R){
    return Q.second < R.second;
}

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){
    int j,q;
    vector<pair<int,int> > Z;
    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),DivConq(mij+1,dr,X));
    for(int i=st;i<=dr;i++)
        if(abs(X[mij].first - X[i].first) <=rez)
            Z.push_back(X[i]);
    sort(Z.begin(), Z.end(),dupay);
    for(int i=1;i<Z.size();i++){
        for(j = i + 1; j <= Z.size() && (j-i) < 6; ++j, ++q){
            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());
    g << setprecision(8) << DivConq(0,n-1,X);

    return 0;
}