Cod sursa(job #1133012)

Utilizator beldeabogdanBogdan Beldea beldeabogdan Data 4 martie 2014 11:33:15
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
#define nmax 100005
#define minim(a,b) (a<b)?(a):(b)
using namespace std;

struct punct {
    int x,y;
};

punct v[nmax];
punct aux[nmax];
int ap;
int n;

bool cmp(punct a,punct b) {
    if (a.x < b.x) return true;
    else if (a.x == b.x) return a.y < b.y;
    else return false;
}

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

double divide(int p,int u) {
    if (u-p == 1) return distanta(v[p],v[u]);
    int mij = (p+u)/2;
    double ds = divide(p,mij);
    double dd = divide(mij+1,u);
    double d = minim(ds,dd);
    int i=p,j=mij+1;
    while (i<mij && j < u) {
        if (v[i].y <= v[j].y && i < mij) {
            aux[++ap] = v[i++];
        } else {
            aux[++ap] = v[j++];
        }
    }
    for (int i=p;i<=u;i++) v[i] = aux[i-p+1];
    for (int i=p;i<=u;i++) {
        if (abs(v[i].x-v[mij].x) <= d) {
            for (int j=i+1;j<=i+8 && j<=u;j++) d = minim(d,distanta(v[i],v[p]));
        }
    }
    return d;
}

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