Cod sursa(job #2696743)

Utilizator PopandauPopandau boomer Popandau Data 16 ianuarie 2021 14:31:47
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.96 kb
#include <iostream>
#include <cmath>
#include <iomanip>
#include <fstream>
using namespace std;

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

typedef struct{
int x,y;
}punct;

void schimb(punct &a,punct &b)
{
    punct aux=a;
    a=b;
    b=aux;
}

int partitie(punct puncte[100],int l,int r)
{
    int i=l-1;
    int pivot=puncte[r].x;
    for(int j=l;j<=r-1;j++)
    {
        if(puncte[j].x<=pivot)
        {
            i++;
            schimb(puncte[i],puncte[j]);
        }
    }
    schimb(puncte[i+1],puncte[r]);
    return i+1;
}

void sortare(punct puncte[100],int l,int r)
{
    if(l<r)
    {
        int pivot=partitie(puncte,l,r);
        sortare(puncte,l,pivot-1);
        sortare(puncte,pivot+1,r);
    }
}

double d(punct a,punct b)
{
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}


double dist(int n,punct puncte[100])
{
    int dp;
    int minim=2147483647;
    for(int i=1;i<=n-1;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
           dp=d(puncte[i],puncte[j]);
           if(dp<minim)
           {
            minim=dp;
           }
        }
    }
    return sqrt(minim);
}

void interclaseaza(int n,punct puncte[100],punct puncte_y[100],int l,int mij,int r)
{
    int i=l;
    int j=mij+1;
    int k=l;
    while(i<=mij&&j<=r)
    {
        if(puncte_y[i].y<puncte_y[j].y)
        {
            puncte[k]=puncte_y[i];
            i++;
        }
        else
        {
            puncte[k]=puncte_y[j];
            j++;
        }
        k++;
    }
    while(i<=mij)
    {
        puncte[k]=puncte_y[i];
        i++;
        k++;
    }
    while(j<=r)
    {
        puncte[k]=puncte_y[j];
        j++;
        k++;
    }
      for(int i=l;i<=r;i++)
      {
          puncte_y[i]=puncte[i];
      }

}

double dist2(int n,punct puncte[100],int l,int r,punct puncte_y[100],punct v[100])
{
    if(r-l==1)
    {
        if(puncte[l].y<puncte[r].y)
        {
            puncte_y[l]=puncte[l];
            puncte_y[r]=puncte[r];
        }
        else
        {
            puncte_y[l]=puncte[r];
            puncte_y[r]=puncte[l];
        }
        return d(puncte[r],puncte[l]);
    }
    if(r-l==2)
    {
        if(puncte[l].y<puncte[l+1].y)
        {
            if(puncte[l+1].y<puncte[r].y)
            {
                puncte_y[l]=puncte[l];
                puncte_y[l+1]=puncte[l+1];
                puncte_y[r]=puncte[r];
            }
            else{
                if(puncte[r].y<puncte[l].y)
                {
                puncte_y[l]=puncte[r];
                puncte_y[l+1]=puncte[l];
                puncte_y[r]=puncte[l+1];
                }
                else
                {
                puncte_y[l]=puncte[l];
                puncte_y[l+1]=puncte[r];
                puncte_y[r]=puncte[l+1];
                }
            }
        }
        else
        {
            if(puncte[l].y<puncte[r].y)
            {
               puncte_y[l]=puncte[l+1];
                puncte_y[l+1]=puncte[l];
                puncte_y[r]=puncte[r];
            }
            else
            {
                if(puncte[r].y<puncte[l+1].y)
                {
                puncte_y[l]=puncte[r];
                puncte_y[l+1]=puncte[l+1];
                puncte_y[r]=puncte[l];
                }
                else
                {
                puncte_y[l]=puncte[l+1];
                puncte_y[l+1]=puncte[r];
                puncte_y[r]=puncte[l];
                }
            }
        }
        double a=d(puncte[l],puncte[l+1]);
        double b=d(puncte[l+1],puncte[r]);
        double c=d(puncte[r],puncte[l]);

        return ((a>b ? b:a)>(b>c ? c:b) ? (b>c ? c:b):(a>b ? b:a));
    }
    int mij=(l+r)/2;
    double ds=dist2(n,puncte,l,mij,puncte_y,v);
    double dd=dist2(n,puncte,mij+1,r,puncte_y,v);
    double df=ds>dd ? dd:ds;
    int k;
    double dn;
    interclaseaza(n,puncte,puncte_y,l,mij,r);
    int vi=0;
    double tmp;
    for(int i=l;i<=r;i++)
    {
        tmp=((puncte[mij].x-puncte_y[i].x)>0 ?  (puncte[mij].x-puncte_y[i].x):-1*(puncte[mij].x-puncte_y[i].x));
        if(tmp<=df)
        {
            vi++;
            v[vi]=puncte[i];
        }
    }
    for(int i=l;i<=vi-1;i++)
    {
        k=r-i>=7 ? 7:r-i;
        for(int j=1;j<=k;j++)
        {
            dn=d(v[i],v[i+j]);
            if(dn<df)
            {
                df=dn;
            }
        }
    }
    return df;
}

void citire(int& n,punct puncte[100])
{
    f>>n;
    for(int i=1;i<=n;i++)
    {
        f>>puncte[i].x>>puncte[i].y;
    }
}

int main()
{
    int n;
    punct puncte[100];
    punct puncte_y[100];
    punct v[100];
    citire(n,puncte);
    double r=dist2(n,puncte,1,n,puncte_y,v);
    /*cout<<endl;
    for(int i=1;i<=n;i++) cout<<puncte_y[i].x<<" "<<puncte_y[i].y<<endl; */
    g<<fixed<<setprecision(6)<<sqrt(r);
    f.close();
    g.close();
    return 0;
}