Cod sursa(job #2067947)

Utilizator Consti.001FMI Dranca Constantin Consti.001 Data 16 noiembrie 2017 23:22:07
Problema Cele mai apropiate puncte din plan Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 2.6 kb
#include<fstream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<iomanip>
#define INF 999999999
using namespace std;

ifstream f("cmap.in");
ofstream g("cmap.out");

class point
{
    double x,y;
    public:
        double read_point()
    {
        f>>x>>y;
        return x;
    }
        double write_point()
    {
        g<<x<<" "<<y<<"\n";
        return x;
    }
        double getx()
        {
            return x;
        }
        double gety()
        {
            return y;
        }
}X,Y;
double dist_min=INF;
bool cmpx(point A, point B)
{
    return A.getx()<B.getx();
}

bool cmpy(point A, point B)
{
    return A.gety()<B.gety();
}
double euclid_dist(point A, point B)
{
    double d1,d2;
    d1=A.getx()-B.getx();
    d2=A.gety()-B.gety();
    return sqrt((d1*d1)+(d2*d2));
}
double get_min(double a, double b)
{
    if(a<=b) return a;
    else return b;
}
double get_pair_of_points(point l[],int st,int dr)
{
    if(dr-st<3)
    {
        double dist_min=INF;
        for(int i=st;i<dr;++i)
            for(int j=i+1;j<=dr;++j)
            {
                double distanta=euclid_dist(l[i],l[j]);
                if(distanta<dist_min)
                {
                    X=l[i];
                    Y=l[j];
                    dist_min=distanta;
                }
            }
        return dist_min;
    }
    else
    {
        int mid=(st+dr)/2;
        double line_L;
        line_L=(l[mid].getx()+l[mid+1].getx())/2;
        double dist_left=get_pair_of_points(l,st,mid);
        double dist_right=get_pair_of_points(l,mid+1,dr);
        double dist_minim=get_min(dist_left,dist_right);
        vector <point> lista_Y;
        int nr_Y=0;
        for(int i=st;i<=dr;++i)
            if(fabs(line_L-l[i].getx())>dist_minim)
            {
                lista_Y.push_back(l[i]);
                nr_Y++;
            }

            sort(lista_Y.begin(),lista_Y.end(),cmpy);

            for(int i=0;i<nr_Y-1;++i)
            {
                for(int j=i+1;j<nr_Y&&j-i<8;++j)
                {
                    double dist_loc=euclid_dist(lista_Y[i],lista_Y[j]);
                    if(dist_loc<dist_minim)
                    {
                        dist_minim=dist_loc;
                    }
                }
            }
        return dist_minim;
    }
    return -1;
}
int main()
{
    int n;
    f>>n;
    point lista[n];
    for(int i=0;i<n;++i)
    {
        lista[i].read_point();
    }
    sort(lista,lista+n,cmpx);

    g<<fixed<<setprecision(6)<<get_pair_of_points(lista,0,n-1);
}