Cod sursa(job #2002128)

Utilizator MaligMamaliga cu smantana Malig Data 18 iulie 2017 18:57:34
Problema Cele mai apropiate puncte din plan Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.86 kb
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <vector>
#include <iomanip>
#include <cmath>
#include <algorithm>

using namespace std;
ifstream in("cmap.in");
ofstream out("cmap.out");

#define ll long long
#define ull unsigned long long
#define pb push_back
const int inf = 1e9 + 5;
const int NMax = 1e5 + 5;

int N;

struct point {
    int x,y;
}v[NMax],aux[NMax];

bool cmp(point,point);
ll solve(int,int);
ll dist(point,point);

int main() {
    in>>N;
    for (int i=1;i <= N;++i) {
        in>>v[i].x>>v[i].y;
    }

    sort(v+1,v+N+1,cmp);

    ll mn = solve(1,N);
    out<<fixed<<setprecision(6)<<sqrt(mn)<<'\n';

    in.close();out.close();
    return 0;
}

ll solve(int st,int dr) {
    if (st >= dr) {
        return inf;
    }
    if (st == dr-1) {
        if (v[st].y > v[dr].y) {
            swap(v[st],v[dr]);
        }

        return dist(v[st],v[dr]);
    }

    ll mij = (st+dr)>>1,
        abscisa = v[mij].x,
        mn = min(solve(st,mij),solve(mij+1,dr));

    int nrAux = 0, i = st, j = mij+1;
    while (i <= mij && j <= dr) {
        if (v[i].y < v[j].y) {
            aux[++nrAux] = v[i++];
        }
        else {
            aux[++nrAux] = v[j++];
        }
    }
    while (i <= mij) {
        aux[++nrAux] = v[i++];
    }
    while (j <= dr) {
        aux[++nrAux] = v[j++];
    }

    nrAux = 0;
    int root = sqrt(mn);
    for (i = st;i <= dr;++i) {
        if (abs(v[i].x - abscisa) <= mn) {
            aux[++nrAux] = v[i];
        }
    }

    for (i=1;i <= nrAux;++i) {
        for (int j=i+1;j <= i+7;++j) {
            mn = min(mn,dist(aux[i],aux[j]));
        }
    }

    return mn;
}

ll dist(point a,point b) {
    return 1LL * (a.x - b.x) * (a.x - b.x) + 1LL * (a.y - b.y) * (a.y - b.y);
}

bool cmp(point a,point b) {
    return a.x < b.x;
}