Cod sursa(job #1133037)

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

struct punct {
    long long 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) + (double)(a.y-b.y)*(a.y-b.y));
}

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

    for (register int i=p;i<u;i++) {
        if (abs(v[i].x-v[mij].x) <= d && i!=mij) {
            for (int j=i+1;v[j].y-v[i].y <= d && j<=u;j++) d = minim(d,distanta(v[i],v[j]));
        }
    }
    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;
}