Cod sursa(job #2074698)

Utilizator OctavMarcoMarcovschi Octavian-Mihai OctavMarco Data 24 noiembrie 2017 21:45:11
Problema Cele mai apropiate puncte din plan Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 2.27 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]);
    d=min( dmin(XS,YS,st,mij-1),dmin(XD,YD,mij,dr));
    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);
    out<<setprecision(20)<<sqrt(dmin(X,Y,X[0].first,X[n-1].first));
    return 0;
}