Cod sursa(job #1585777)

Utilizator gapdanPopescu George gapdan Data 31 ianuarie 2016 14:34:08
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <fstream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define NMAX 100005

using namespace std;

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

int n,i,j;
bool cmp(punct r,punct p)
{
    return (p.y<r.y);
}

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;
    int mij,l,r,k,i,j;
    double rez1,rez2;
    mij=(st+dr)/2;
    rez1=divide(st,mij);
    rez2=divide(mij+1,dr);
    if(rez2<rez1) rez1=rez2;

    //interclasam punctele
    l=st;r=mij+1;k=0;
    while(l<=mij || r<=dr)
    {
        if(r > dr || (l<=mij && v[l].y<v[r].y)) {aux[++k]=v[l];++l;}
            else {aux[++k]=v[r];++r;}
    }

    k=0;
    for(i=st;i<=dr;++i)
        v[i]=aux[++k];

    //verificam daca exista distanta minima intre puncte situate pe parti diferite ale dreptei

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

}

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("%.10f",sol);
    return 0;
}