Cod sursa(job #1624485)

Utilizator ASTELOTudor Enescu ASTELO Data 2 martie 2016 11:29:48
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
struct eu{int x,y;};
eu v[100001];
int i,j,n,m,k;
double minim=100000000;
bool sorting (eu a,eu b)
    {
    return a.x<b.x;
    }
double dist(eu a,eu b)
    {
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
    }
void divide(int st,int dr)
    {
    int l1,l2,mid,i,j;
    if(dr-st<=2)
        {
        for(i=st;i<dr;i++)
            for(j=i+1;j<=dr;j++)
                {
                double x;
                x=dist(v[i],v[j]);
                if(x<minim)
                    minim=x;
                }
        }
    else
        {
        mid=(dr+st)/2;
        divide(st,mid);
        divide(mid+1,dr);
        int k=max(1,mid-4),k1=min(mid+4,n);
        for(i=k;i<k1;i++)
            for(j=i+1;j<=k1;j++)
                {
                double x;
                x=dist(v[i],v[j]);
                if(x<minim)
                    minim=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,sorting);
divide(1,n);
printf("%.6lf",minim);
return 0;
}