Cod sursa(job #2521168)

Utilizator vladsergheiSerghei Vlad Andrei vladserghei Data 10 ianuarie 2020 14:56:35
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.09 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <float.h>
#include <stdlib.h>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
struct punct
{
    int x;
    int y;
};
float distanta(punct a,punct b)
{
    float d=sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
    return d;
}
int compX(const void* a,const void* b)
{
    punct *a1=(punct*)a;
    punct *b1=(punct *)b;
    return a1->x-b1->x;
}
int compY(const void* a,const void* b)
{
    punct *a1=(punct*)a;
    punct *b1=(punct *)b;
    return a1->y-b1->y;
}
float minDistSubsir(punct v[],int leng,float dist)
{
    float minDist=dist;
    for(int i=0;i<leng;i++)
        for(int j=i+1;j<leng&&(v[j].y-v[i].y)<minDist;j++)
            if (distanta(v[i],v[j])<minDist)
                minDist=distanta(v[i],v[j]);
    return minDist;
}
float max3p(punct v[],int n)
{
    float mini=FLT_MAX;
    for (int i=0;i<n;i++)
        for(int j=i+1;j<n;j++)
            if(distanta(v[i],v[j])<mini)
                mini=distanta(v[i],v[j]);
    return mini;
}
float min(float x, float y)
{
    return (x < y)? x : y;
}
float minDist(punct vx[],punct vy[],int n)
{
    if(n<=3)
        return max3p(vx,n);
    int m=n/2;
    punct M=vx[m];

    punct vys[m+1];
    punct vyd[n-m-1];
    int s=0,d=0;
    for(int i=0;i<n;i++)
    {
      if (vy[i].x<=M.x)
         vys[s++]=vy[i];
      else
         vyd[d++]=vy[i];
    }
    float ds=minDist(vx,vys,m);
    float dd=minDist(vx+m,vyd,n-m);

    float dist=min(ds,dd);

    punct sir[n];
    int j=0;
    for (int i=0;i<n;i++)
        if (abs(vy[i].x-M.x)<dist)
            {
                sir[j]=vy[i];
                j++;
            }

    return min(dist,minDistSubsir(sir,j,dist));

}
int main()
{
    int n;
    fin>>n;
    punct vx[n],vy[n];
    for(int i=0;i<n;i++)
    {
        fin>>vx[i].x>>vx[i].y;
        vy[i].x=vx[i].x;
        vy[i].y=vx[i].y;
    }

    qsort(vx,n,sizeof(punct),compX);
    qsort(vy,n,sizeof(punct),compY);
    float d=minDist(vx,vy,n);
    fout<<d;
    return 0;
}