Cod sursa(job #1586615)

Utilizator margikiMargeloiu Andrei margiki Data 1 februarie 2016 14:49:34
Problema Cele mai apropiate puncte din plan Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
# include <fstream>
# include <algorithm>
# include <cstring>
# include <cmath>
# include <iomanip>
# define mp make_pair
# define f first
# define s second
# define NR 100005
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
pair <long long, long long> a[NR], aux[NR];
bool cmp (pair <long long, long long> a, pair <long long, long long> b) {
    return (a.s < b.s);
}
int i,j,n,m;
double dist (pair <long long, long long> a, pair <long long, long long> b) {
    return (sqrt((double)((a.f-b.f)*(a.f-b.f) + (a.s-b.s)*(a.s-b.s))));
}
double divide (int st, int dr) {
    double minn=INFINITY;
    int i,j,mij;
    if (dr-st<=2) {
        for (i=st; i<dr; ++i)
            for (j=i+1; j<=dr; ++j)
                minn=min(minn, dist(a[i], a[j]));
        for (i=st; i<dr; ++i)
            for (j=i+1; j<=dr; ++j)
                if (a[i].s >= a[j].s) swap(a[i], a[j]);
        return minn;
    }
    mij=(st+dr)/2;
    divide (st, mij);
    divide (mij+1, dr);
    // interclasez
    merge (a+st, a+mij+1, a+mij+1, a+dr+1, aux+1, cmp);
    //copiez
    for (i=st; i<=dr; ++i)
        a[i]=aux[i-st+1];

    //acum verific cu urmatoarele 7 puncte
    for (i=st; i<=dr; ++i)
        for (j=i+1; j<=i+7 && j<=dr; ++j)
            minn=min(minn, dist(a[i], a[j]));

    return minn;
}
int main ()
{
    f>>n;
    for (i=1; i<=n; ++i)
        f>>a[i].f>>a[i].s;
    sort (a+1, a+n+1);

    g<<fixed<<setprecision(6)<<divide (1, n)<<"\n";


    return 0;
}