Cod sursa(job #2487968)

Utilizator stan_flaviusStan Flavius Stefan stan_flavius Data 5 noiembrie 2019 21:56:46
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.8 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
#define nmax 100001

using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");

struct punct
{
    int x,y;
};

punct pct[nmax];
int n;

bool cmp_x(punct A,punct B)
{
    if(A.x==B.x) return A.y<B.y;
    return A.x<B.x;
}

bool cmp_y(punct A,punct B)
{
    return A.y<B.y;
}

double calc_dist(punct A,punct B)
{
    return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}

double search_dist_min(punct P[],int left,int right)
{
    double mn=1e9;
    for(int i=left; i<right; i++)
        for(int j=i+1; j<=right; j++)
            {
                //fout<<P[i].x<<" "<<P[i].y<<" "<<P[j].x<<" "<<P[j].y<<" "<<calc_dist(P[i],P[j])<<"\n";
                if(calc_dist(P[i],P[j])<mn) mn=calc_dist(P[i],P[j]);
            }
    return mn;
}

double sol(punct P[],int left,int right)
{
    if(right-left<=3)
        return search_dist_min(P,left,right);

    int mid=(right-left)/2;

    double dist_left=sol(P,left,mid);
    double dist_right=sol(P,mid+1,right-1);

    double dist_min=min(dist_left,dist_right);

    int val=P[mid].x;
    punct pct_closest[nmax];
    int ct=0;
    for(int i=left; i<=right; i++)
        if(abs(P[i].x-val)<dist_min)
            pct_closest[++ct]=P[i];
    sort(pct_closest+1,pct_closest+ct+1,cmp_y);

    double dist_min_2=0;
    for(int i=1; i<=ct-7;  i++)
        for(int j=i+1; j<=i+7; j++)
            if(calc_dist(P[i],P[j])<dist_min_2) dist_min_2=calc_dist(P[i],P[j]);

    //fout<<dist_min<<" "<<dist_min_2<<"\n";
    return min(dist_min,dist_min);
}

int main()
{
    fin>>n;
    for(int i=0; i<n; i++)
        {
            fin>>pct[i].x>>pct[i].y;
        }
    sort(pct,pct+n,cmp_x);
    fout<<sol(pct,0,n-1);
    return 0;
}