Cod sursa(job #2100509)

Utilizator Versin_ElenaVersin Elena Versin_Elena Data 5 ianuarie 2018 19:11:11
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 3.04 kb
#include <iostream>
#include<fstream>
#include<stdlib.h>
#include<cmath>
#include<algorithm>
#include<iomanip>
#define INF 1000000000000000000000
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
struct punct
{
    int x;
    int y;
};

punct *vect,*X,*Y;
int nr;

void afisare(punct *vect,int inc, int dim)
{
    for(int i=inc; i<=dim; i++)
        cout<<vect[i].x<<" "<<vect[i].y<<endl;
    cout<<endl;
}


int compare_abs(const void* a, const void* b)
{

    punct* A=(punct*)a;
    punct* B=(punct*)b;
    if(A->x<B->x) return -1;
    if(A->x==B->x) return 0;
    if(A->x>B->x) return 1;

}
int compare_ord(const void* a, const void* b)
{

    punct* A=(punct*)a;
    punct* B=(punct*)b;
    if(A->y<B->y) return -1;
    if(A->y==B->y) return 0;
    if(A->y>B->y) return 1;

}
double distanta(punct a, punct b)
{
    double z;
    z=sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
    return z;
}

double DivImp( int st, int dr,punct *Y)
{
    if(st==dr) return INF;
    if(dr-st+1==2)
    {
        double z=distanta(X[st],X[dr]);
        return z;
    }

    if(dr-st+1==3)
    {
        double aux1,aux2,aux3;
        aux1=distanta(X[st],X[st+1]);
        aux2=distanta(X[st+1],X[dr]);
        aux3=distanta(X[st],X[dr]);
        double minim;
        if(aux1<aux2) minim=aux1;
        else minim=aux2;
        if(aux3<minim) minim=aux3 ;
        return minim;
    }
    int mij=(st+dr)/2;
    int n=dr-st+1;
    punct *SY,*DY,*LY;
    SY=new punct[nr+1];
    DY=new punct[nr+1];
    LY=new punct[nr+1];
    int dim1,dim2,dim3;
    dim1=dim2=dim3=-1;
    for(int i=0; i<n; i++)
        if(Y[i].x<=X[mij].x)
        {
            dim1++;
            SY[dim1]=Y[i];
        }
        else
        {
            dim2++;
            DY[dim2]=Y[i];
        }

    double d1=DivImp(st,mij,SY);
    double d2=DivImp(mij+1,dr,DY);
    double d=min(d1,d2);
    for(int i=0; i<n; i++)
        if((abs(Y[i].x-X[mij].x)<=d)&& abs(Y[i].y-X[mij].y)<=d)
        {
            dim3++;
            LY[dim3]=Y[i];
        }
    double d3=distanta(LY[0],LY[1]);
    double dist_aux=0;
    for(int i=0; i<dim3; i++)
        for(int j=i+1; j<=dim3; j++)
        {
            dist_aux=distanta(LY[i],LY[j]);
            if(dist_aux<d3) d3=dist_aux;
        }
    d=min(d,d3);
    delete[]SY;
    delete[]DY;
    delete[]LY;
    return d;

}

int main()
{
    f>>nr;
    vect=new punct[nr+1];
    X=new punct[nr+1];
    Y=new punct[nr+1];
    for(int i=0; i<nr; i++)
    {
        f>>vect[i].x>>vect[i].y;
        X[i]=vect[i];///vectorul in care o sa le am sortate dupa abscisa
        Y[i]=vect[i];///vectorul in care o sa le am sortate dupa ordonata
    }

    qsort(X,nr,sizeof(punct),compare_abs);///ordonez vectorul X dupa abscisa
    qsort(Y,nr,sizeof(punct),compare_ord);///ordonez vectorul Y dupa ordonata
    g<<fixed<<setprecision(6)<<DivImp(0,nr-1,Y);


    delete[] vect;
    delete[] X;
    delete[] Y;

    f.close();
    g.close();
    return 0;
}