Cod sursa(job #2074681)

Utilizator OctavMarcoMarcovschi Octavian-Mihai OctavMarco Data 24 noiembrie 2017 21:28:19
Problema Cele mai apropiate puncte din plan Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 2.77 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <algorithm>
#include <math.h>
#include <float.h>
#include <iomanip>

using namespace std;

bool dupaX(pair<int,int> a,pair<int,int> b){
    if(a.first<b.first)
        return 1;
    else
        if(a.first==b.first)
            if(a.second<b.second)
                return 1;
    return 0;
}
bool dupaY(pair<int,int> a,pair<int,int> b){
    if(a.second<b.second)
        return 1;
    else
        if(a.second==b.second)
            if(a.first<b.first)
                return 1;
    return 0;
}

double calc_dist(pair<int,int> x, pair<int,int> y)
{
    return (pow(x.first-y.first,2)+pow(x.second-y.second,2));
}

double dmin(deque<pair<int,int> > X, deque<pair<int,int> > Y, double st, double dr){
    double d=DBL_MAX;
    if(X.size()<4){
        double dn;
        for(int i=0;i<2;i++)
            for(int j=i+1;j<4;j++){
                dn=calc_dist(X[i],X[j]);
                if(dn<d) d=dn;
            }
    return d;
    }
    double mij=X.size()/2;
    deque<pair<int,int> > XS,YS,XD,YD;
    for(int i=0;i<mij;i++)
        XS.push_back(X[i]);

    for(int i=0;i<X.size();i++)
        if(Y[i].first>=X[0].first && Y[i].first<X[mij].first)
            YS.push_back(Y[i]);

    for(int i=mij;i<X.size();i++)
        XD.push_back(X[i]);

    for(int i=0;i<X.size();i++)
        if(Y[i].first>=X[mij].first && Y[i].first<=X[X.size()-1].first)
            YD.push_back(Y[i]);
    /*for(int i=0;i<mij;i++)
        cout<<YS[i].first<<" "<<YS[i].second<<endl;
    cout<<endl<<endl;*/
    d=min( dmin(XS,YS,st,mij),dmin(XD,YD,mij,dr)); // AICI mij-1 ??
    deque<pair<int,int> > YM;
    for(int i=0;i<X.size();i++)
        if(Y[i].first>(X[mij].first-sqrt(d)) && Y[i].first<(X[mij].first+sqrt(d)))
            YM.push_back(Y[i]);
    for(int i=0;i<YM.size();i++)
        for(int j=i+1;j<=i+7 && j<YM.size();j++)
            d=min(d,calc_dist(YM[i],YM[j]));
    return d;
}

int main(){
    ifstream in("cmap.in");
    ofstream out("cmap.out");
    int n;
    in>>n;
    deque<pair<int,int> > X,Y;
    int x,y;
    for(int i=0;i<n;i++){
        in>>x>>y;
        X.push_back(make_pair(x,y));
        Y.push_back(make_pair(x,y));
    }
    sort(X.begin(),X.end(),dupaX);
    sort(Y.begin(),Y.end(),dupaY);
     /*deque<pair<int,int> >::iterator it=a.begin();
    for( it;it!=a.end();++it)
        cout<<a[it].first<<endl;*/
    /*for(int i=0;i<n;i++)
        cout<<X[i].first<<" "<<X[i].second<<endl;
    cout<<endl<<endl;
    for(int i=0;i<n;i++)
        cout<<Y[i].first<<" "<<Y[i].second<<endl;
        //cout<<a.first<<" "<<a.second<<endl;
    cout<<endl<<endl;*/
    //cout<<X.size();
    out<<setprecision(10)<<sqrt(dmin(X,Y,X[0].first,X[n-1].first));
    return 0;
}