Cod sursa(job #2079878)

Utilizator bazooka01Florin Bogdan Mihalache bazooka01 Data 1 decembrie 2017 22:29:45
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3.01 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#define INF 1<<30
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 = INF, d1, d2, d3;
    if(dr - st < 4) {
//        for(int i=st; i<=dr; i++) cout<<Y[i].x<<" "<<Y[i].y<<"\n";
//        cout<<"\n";
        sort(Y.begin()+st, Y.begin()+dr+1, compy);
//        for(int i=st; i<=dr; i++) cout<<Y[i].x<<" "<<Y[i].y<<"\n";
//        cout<<"\n\n";
//        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]) );
//        }
        for(int i=st; i<dr; i++)
        {
            for(int j=i+1; j<=dr; j++)
            {
                d3 = calc_dist(X[i], X[j]);
                d = min(d, d3);
            }
        }
    } else {
        int mij = (st + dr)/2, j, i;
        d1 = Divide(st, mij);
        d2 = Divide(mij+1, dr);
        d3 = d = min( d1, d2 );
        //Interclasare
//        for(i=st; i<=dr; i++) cout<<Y[i].x<<" "<<Y[i].y<<"\n";
//        cout<<"\n";
        inplace_merge( Y.begin()+st, Y.begin()+mij+1, Y.begin()+dr+1, compy );
//        for(i=st; i<=dr; i++) cout<<Y[i].x<<" "<<Y[i].y<<"\n";
//        cout<<"\n\n";
        //
        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++)
            {
                double daux = calc_dist( LY[i], LY[j] );
                if( daux < d3 ) d3 = daux;
            }

        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);
    for(int i=0; i<X.size(); i++) cout<<X[i].x<<" "<<X[i].y<<"\n";
    cout<<"\n";
    //for(int i=0; i<Y.size(); i++) cout<<Y[i].x<<" "<<Y[i].y<<"\n";
}

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