Cod sursa(job #2068514)

Utilizator Consti.001FMI Dranca Constantin Consti.001 Data 18 noiembrie 2017 00:10:19
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.69 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
{
    long long x,y;
    public:
        long long read_point()
    {
        f>>x>>y;
        return x;
    }
        long long write_point()
    {
        g<<x<<" "<<y<<"\n";
        return x;
    }
        long long getx()
        {
            return x;
        }
        long long gety()
        {
            return y;
        }
}X,Y;
long long 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();
}
long long euclid_dist(point A, point B)
{
    long long d1,d2;
    d1=A.getx()-B.getx();
    d2=A.gety()-B.gety();
    return (d1*d1)+(d2*d2);
}
long long get_min(long long a, long long b)
{
    if(a<=b) return a;
    else return b;
}
long long get_pair_of_points(point l[],int st,int dr)
{
    if(dr-st<3)
    {
        long long dist_min=INF;
        for(int i=st;i<dr;++i)
            for(int j=i+1;j<=dr;++j)
            {
                long long 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;
        long long line_L;
        line_L=(l[mid].getx()+l[mid+1].getx())/2;
        long long dist_left=get_pair_of_points(l,st,mid);
        long long dist_right=get_pair_of_points(l,mid+1,dr);
        long long 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)
            {
                int length=1;
                for(int j=i+1;j<nr_Y&&length<8;++j)
                {
                    long long 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)<<sqrt(get_pair_of_points(lista,0,n-1));
}