Cod sursa(job #2617552)

Utilizator horia_mercanHoria Mercan horia_mercan Data 21 mai 2020 22:52:51
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.48 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#define LIM_MAX 10000

using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
struct Point{
    int x,y;
};

bool compare_Ox(Point a,Point b);
bool compare_Oy(Point a,Point b);

float min_(float x, float y){
    return (x<y)? x:y;
}

float distanta(Point a , Point b);
float brute_force(Point p[],int n);
float verif_banda(Point p[],int n, float d);
float min_distance(Point px[],Point py[],int n);

int main()
{
    int n,i,x0,y0;
    fin>>n;
    Point p[1000],px[1000],py[1000],temp;
    for(i=0;i<n;i++){
        fin>>x0>>y0;
        temp.x=x0;temp.y=y0;
        p[i]=px[i]=py[i]=temp;
    }
    sort(px,px+n,compare_Ox);
    sort(py,py+n,compare_Oy);
    fout<<min_distance(px,py,n);;
}


bool compare_Ox(Point a,Point b){
    if(a.x == b.x) return (a.y<=b.y);
    return (a.x<b.x);
}
bool compare_Oy(Point a,Point b){
    if(a.y == b.y) return (a.x<=b.x);
    return (a.y<b.x);
}

float distanta(Point a , Point b){
    float d = (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y);
    d=sqrt(d);
    return d;
}

float brute_force(Point p[],int n){
    int i,j;
    float minim = LIM_MAX;;
    for(i=0;i<n;i++){
        for(j=i+1;j<n;j++){
            if(distanta(p[i],p[j])<minim)
                minim=distanta(p[i],p[j]);
        }
    }
    return minim;
}
float verif_banda(Point p[],int n, float d){
    float minim=d;
    int i,j;

    sort(p,p+n,compare_Oy);

    for( i=0;i<=n-1;i++){
        for(j=i+1; j<=n-1 && (p[j].y-p[i].y)<minim ;j++){
            if(distanta(p[i],p[j])<minim)
                minim=distanta(p[i],p[j]);
        }
    }

    return minim;
}

float min_distance(Point px[],Point py[],int n){
    if(n<=3) return brute_force(px,n);

    int mij = n/2;
    Point p_left[mij+1],p_right[mij+1]; // punctele vor fi ordonate crescator dupa y
                                        // in stanga si dreapta
    int n_left=0,n_right = 0;
    for(int i=0;i<n;i++){  // impartim array-ul de y in 2 vectori
        if(py[i].x<=px[mij].x && n_left<mij)
            p_left[n_left++]=py[i];
        else
            p_right[n_right++]=py[i];
    }
    float dl=min_distance(px,p_left,mij);
    float dr=min_distance(px,p_right,n-mij);

    float d=min_(dl,dr);

    Point b[n];
    int j=0;
    for(int i=0;i<=n-1;i++){
        if( abs(py[i].x - px[mij].x)<d )
            {b[j]=py[i];j++;}
    }
    return verif_banda(b,j,d);
}