Cod sursa(job #2100349)

Utilizator Versin_ElenaVersin Elena Versin_Elena Data 5 ianuarie 2018 15:43:24
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 2.93 kb
#include <iostream>
#include<fstream>
#include<stdlib.h>
#include<cmath>
#include<algorithm>
#include<iomanip>
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 dim)
{
    for(int i=0;i<nr;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(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],X[dr]);
               aux3=distanta(X[st+1],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=st;i<=dr;i++)
      if(abs(Y[i].x-X[mij].x)<=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=max(1,i-7);j<i;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 vectoeul Y dupa ordonata

    g<<fixed<<setprecision(6)<<DivImp(0,nr-1,Y);


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

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