Cod sursa(job #1233052)

Utilizator lehman97Dimulescu David lehman97 Data 24 septembrie 2014 16:29:43
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>

using namespace std;

FILE *f=fopen("cmap.in","r");
FILE *g=fopen("cmap.out","w");


struct vec
{
    int x,y;
}v[100001];

/*double mn(double a, double b)
{
    if(a-b<1e-5)
    return a;
    else return b;
}*/
double dist(vec a, vec b) {
    return sqrt((a.x-b.x) * (a.x-b.x) + (a.y - b.y) * (a.y - b.y));
}

int n,i;

bool cmp(vec i, vec j)
{

    /*if(i.x==j.x)return i.y<j.y; else*/ return i.x<j.x;
}

/*double divide(int l, int r)
{
    int m=(l+r)/2;
    if(r==l+2)
    {
        return mn(dist(v[l],v[l+1]),dist(v[l+1],v[l+2]));
    }
    if(r==l+1)
    {
        return dist(v[l],v[l+1]);

    } else return mn((divide(l,m)),divide(m+1,r));
}*/
double divide(int l, int r) {
    if (r-l+1<= 3) {
        return min(dist(v[l],v[l+1]), min(dist(v[l],v[l+2]), dist(v[l+1],v[l+2])));
    } else {
        int m=(l+r)/2;
        double s=min(divide(l,m),divide(m,r)),s1;
        s1=s;
        for(int i=m;i>=l && v[m].x-v[i].x<=s;i--)
            for (int j=1;j<=7 && i+j<=r;j++) {
                s1= min(s1,dist(v[i],v[i+j]));
            }
        return s1;
    }
}

int main()
{
    fscanf(f,"%d",&n);
    for(i=1;i<=n;i++)
    fscanf(f,"%d%d",&v[i].x,&v[i].y);
    sort(v+1,v+n+1,cmp);
    fprintf(g,"%.6lf",divide(1,n));
    fclose(g);
    return 0;
}