Cod sursa(job #2074191)

Utilizator Consti.001FMI Dranca Constantin Consti.001 Data 24 noiembrie 2017 10:36:52
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3.21 kb
#include<fstream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<iomanip>
#include<iostream>
#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;
    }
        bool setxy(int a,int b)
        {
            x=a;
            y=b;
            return true;
        }
        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, point ly[])
{
    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;

        point Px[mid+1],Py[dr-mid-1];
        int nl=0;
        int nr=0;

        for(int i=st;i<=dr;++i)
        {
            if(ly[i].getx()<=line_L)
            {
                  Px[nl].setxy(ly[i].getx(),ly[i].gety());
                  ++nl;
            }
            else
            {
                Py[nr].setxy(ly[i].getx(),ly[i].gety());
                ++nr;
            }
        }


        double dist_left=get_pair_of_points(l,st,mid,Px);
        double dist_right=get_pair_of_points(l,mid+1,dr,Py);
        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-ly[i].getx())>dist_minim)
            {
                lista_Y.push_back(ly[i]);
                nr_Y++;
            }

            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];
    point ly[n];
    for(int i=0;i<n;++i)
    {
        lista[i].read_point();
        ly[i].setxy(lista[i].getx(),lista[i].gety());
    }
    sort(lista,lista+n,cmpx);
    sort(ly,ly+n,cmpy);


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