Cod sursa(job #2074053)

Utilizator bazooka01Florin Bogdan Mihalache bazooka01 Data 24 noiembrie 2017 01:07:20
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.49 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

struct coord {
    double x, y;
};

bool compx(coord A, coord B) {
    if( A.x == B.x ) return ( A.y < B.y );
    return ( A.x < B.x );
}
bool compy(coord A, coord B) {
    return ( A.y < B.y );
}


class Plan
{
    int n;
    vector<coord> X, Y;
public:
    Plan(ifstream&);
    double calc_dist(coord, coord);
    double pereche_minima() { return Divide(0, n-1); }
    double Divide(int, int);
};

double Plan::Divide(int st, int dr)
{
    double d, d1, d2, d3;
    if(dr - st < 4) {
        sort(Y.begin()+st, Y.begin()+st+dr-1, compy);
        d = min( calc_dist(X[st], X[st+1]), calc_dist(X[st], X[st+2]) );
        d = min( d, calc_dist(X[st+1], X[st+2]) );
        if(dr - st == 3) {
            d = min( d, calc_dist(X[st], X[st+3]) );
            d = min( d, calc_dist(X[st+1], X[st+3]) );
            d = min( d, calc_dist(X[st+2], X[st+3]) );
        }
    } else {
        int mij = (st + dr)/2;
        d1 = Divide(st, mij);
        d2 = Divide(mij+1, dr);
        d3 = d = min( d1, d2 );
        //Interclasare

        vector<coord> aux(Y.begin()+st, Y.begin()+st+dr);
        int i = st, j = mij+1, contor = st;
        while(i <= mij && j <= dr) {
            if( aux[i].y < aux[j].y ) Y[contor++] = aux[i++];
            else Y[contor++] = aux[j++];
        }
        while(i <= mij) Y[contor++] = aux[i++];
        while(j <= dr) Y[contor++] = aux[j++];
        //
        vector<coord> LY;
        for(i = st; i <= dr; i++)
            if( abs( X[mij].x - Y[i].x ) <= d ) LY.push_back( Y[i] );
        for(i = 0; i<LY.size()-1; i++)
            for(j=i+1; j<LY.size() && ( LY[j].y - LY[i].y < d3 ); j++)
                if( calc_dist( LY[i], LY[j] ) < d3 ) d3 = calc_dist( LY[i], LY[j] );
        d = min( d, d3 );
        //cout<<"sal";
    }
    return d;
}

double Plan::calc_dist(coord A, coord B) {
    return sqrt( (B.x - A.x)*(B.x - A.x) + (B.y - A.y)*(B.y - A.y) );
}

Plan::Plan(ifstream& fin)
{
    fin>>n;
    for(int i=1; i<=n; i++)
    {
        coord aux;
        fin>>aux.x>>aux.y;
        X.push_back(aux);
        Y.push_back(aux);
    }
    sort(X.begin(), X.end(), compx);
    sort(Y.begin(), Y.end(), compx);
}

int main()
{
    ifstream fin("cmap.in");
    ofstream fout("cmap.out");
    Plan plan(fin);
    fin.close();
    fout<<plan.pereche_minima();
    fout.close();
    return 0;
}