Cod sursa(job #1639872)

Utilizator gapdanPopescu George gapdan Data 8 martie 2016 14:28:29
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
#define NMAX 100009

using namespace std;

struct punct
{
    int x,y;
}v[NMAX],aux[NMAX];

int n,i;

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

double divide(int st,int dr)
{
    if(st == dr) return 1e10;
    double rez1,rez2,med;
    int p1,p2,poz,i,j;
    int mij=(st+dr)/2;

    med=v[mij].x;
    rez1=divide(st,mij);
    rez2=divide(mij+1,dr);
    if(rez2 < rez1) rez1=rez2;
    p1=st;p2=mij+1;poz=0;
    //interclasez vectorii
    while(p1 <=mij || p2 <= dr)
    {
        if(p2 > dr || (p1 <= mij && v[p1].y < v[p2].y )) {aux[++poz]=v[p1];++p1;}
            else {aux[++poz]=v[p2];++p2;}
    }
    poz=0;
    for(i=st;i<=dr;++i)
        v[i]=aux[++poz];

    poz=0;
    for(i=st;i<=dr;++i)
        if(v[i].x <= med + rez1 && v[i].x >= med - rez1) aux[++poz]=v[i];

    for(i=1;i<=poz;++i)
        for(j=i+1; j<=poz && aux[j].y-aux[i].y < rez1; ++j)
        {
            rez2=dist(aux[i],aux[j]);
            if(rez2 < rez1) rez1=rez2;
        }
 return rez1;
}

bool cmp(punct r,punct p)
{
    return (r.x>p.x);
}

int main()
{
    freopen("cmap.in","r",stdin);
    freopen("cmap.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;++i) scanf("%d%d",&v[i].x,&v[i].y);
    sort(v+1,v+n+1,cmp);
    double sol=divide(1,n);
    printf("%.10lf\n",sol);
    return 0;
}