Cod sursa(job #2485502)

Utilizator andrei.busuiocAndrei Busuioc andrei.busuioc Data 1 noiembrie 2019 18:11:53
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.52 kb
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cmath>
#include <climits>
#include <fstream>

using namespace std;

struct punct{
    int x,y;
    int id;
};

double length(punct a,punct b){
    double rv;
    rv=sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) );
    return rv;
}

bool cmpP(punct a,punct b){
    if(a.x!=b.x)
        return a.x<b.x;
    else
        return a.y<b.y;
}

int rec(vector<punct> P,int s,int d){
    int a,b;
    if(d/2 - s>1)
        a=rec(P,s,d/2);
    else{
        return length(P[s],P[d/2]);
    }

    if(d - d/2 + 1>1)
        b=rec(P,d/2 + 1,d);
    else
        return length(P[d/2 + 1],P[d]);
    return min(a,b);
}

int main()
{
    ifstream in("cmap.in");
    ofstream out("cmap.out");
    int n;
    in>>n;
    punct aux;
    double x;
    vector <punct> P;
    vector <punct> Y;
    for(int i=1;i<=n;i++){
        in>>aux.x>>aux.y;
        aux.id=i;
        P.push_back(aux);
    }
    sort(P.begin(),P.end(),cmpP);
    int midLine=P[n/2].x;
    int s=0,d=n-1;

    int r=rec(P,s,d);

    for(int i=0;i<n;i++){
        aux.x=midLine;
        aux.y=P[i].y;
        x=length(P[i],aux);
        if(x<=r)
            Y.push_back(P[i]);
    }
    double MIN=INT_MAX;
    for(int i=0;i<Y.size()-1;i++){
        for(int j=i+1;j<i+7 && j<Y.size();j++){
            x=length(Y[i],Y[j]);
            if(x<MIN)
                MIN=x;
        }
    }
    out<<setprecision(8)<<MIN;

    return 0;
}