Cod sursa(job #2070928)

Utilizator valentinasociuSociu Georgiana-Valentina valentinasociu Data 20 noiembrie 2017 00:50:02
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3.11 kb
#include <iostream>
#include <stdlib.h>
#include <math.h>
#include <fstream>
#include <iomanip>
#include <climits>
using namespace std;
struct point
{
    int x, y;
};

struct cuplu
{
    point unu, doi;
};
cuplu a,b;
point pct1, pct2, aux1, aux2;
int compx(const void* a, const void* b)
{
    point *p1 = (point *)a;
    point *p2 = (point *)b;
    return (p1->x - p2->x);
}

int compy(const void* a, const void* b)
{
    point *p3 = (point *)a;
    point *p4 = (point *)b;
    return (p3->y - p4->y);
}

//calculul distantei
float dist(point a, point b)
{
    return sqrt((a.x - b.x)*(a.x - b.x)+(a.y - b.y)*(a.y - b.y));
}

float verif(point s[], int dim, float d)
{
    float min=d;
    for(int i=0;i<dim-1;i++)
        for(int j=i+1;j<dim&&(s[j].y-s[i].y)<min;j++)
            if (dist(s[i],s[j])<min)
                {
                    min=dist(s[i],s[j]);
                    if(s[i].x!=aux1.x&&s[i].y!=aux1.y&&s[j].x!=aux2.x&&s[j].y!=aux2.y)
                    {   aux1=s[i];
                        aux2=s[j];
                        b.unu=aux1;
                        b.doi=aux2;
                    }
                }
    return min;
}
float mn=INT_MAX;
float dei(point X[], point Y[], int n)
{
    if(n<=3)
    {
        int i, j;
        for(i=0;i<n-1;i++)
        for(j=i+1;j<n;j++)
            if(dist(X[i],X[j])<mn)
    {
        mn=dist(X[i],X[j]);
        pct1=X[i];
        pct2=X[j];
        a.unu=pct1;
        a.doi=pct2;
    }
    return mn;
    }
    int mid=n/2;
    point midp=X[mid];
    point pyleft[mid+1];
    point pyright[n-mid-1];
    int l=0,r=0;
    for(int i=0;i<n;i++)
    {
      if (Y[i].x<=midp.x)
         pyleft[l++]=Y[i];
      else
         pyright[r++]=Y[i];
    }
    float left=dei(X,pyleft,mid);
    float right=dei(X+mid,pyright,n-mid);
    float minim=min(left,right);
    point closest[n];
    int j=0;
    for(int i=0;i<n;i++)
        if(abs(Y[i].x-midp.x)<minim)
            {
                closest[j]=Y[i];
                j++;
            }

    if(minim<verif(closest, j, minim))
    {
        pct1=a.unu;
        pct2=a.doi;
    }
    else if(verif(closest, j, minim)<minim)
        {
            pct1=b.unu;
            pct2=b.doi;
        }
    return min(minim, verif(closest, j, minim));
}

int main()
{
    int n;
    ifstream f("cmap.in");
    ofstream g("cmap.out");
    f>>n;
    point puncte[n];
    for(int i=0;i<n;i++)
    {
        point a;
        f>>a.x>>a.y;
        puncte[i]=a;
    }
    aux1.x=aux1.y=aux2.x=aux2.y=INT_MAX;
    a.unu.x=a.unu.y=a.doi.x=a.doi.y=b.unu.x=b.unu.y=b.doi.x=b.doi.y=INT_MAX;
    point X[n];
    point Y[n];
    for(int i=0;i<n;i++)
    {
        X[i]=puncte[i];
        Y[i]=puncte[i];
    }
    qsort(X, n, sizeof(point), compx);
    qsort(Y, n, sizeof(point), compy);
    //for(int i=0;i<n;i++)
      //  cout<<X[i].x<<" ";

    float distanta=dei(X,Y,n);
    g<<fixed<<setprecision(6)<<distanta;
    //g<<"Distanta este "<<distanta<<" intre punctele ("<<pct1.x<<" "<<pct1.y<<") si  ("<<pct2.x<<" "<<pct2.y<<").";
    return 0;
}