Cod sursa(job #1593264)

Utilizator BugirosRobert Bugiros Data 8 februarie 2016 14:46:41
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.74 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>
using namespace std;

const int MAXN = 100005;
const long long INF = 1ll << 62;

ifstream in("cmap.in");
ofstream out("cmap.out");

struct punct
{
    int x,y;
};

int n;


punct pct1[MAXN];
punct pct2[MAXN];

bool ordine_dupa_x(punct a, punct b)
{
    if (a.x < b.x);
        return true;
    if (a.x > b.x);
        return false;
    return a.y < b.y;
}

bool ordine_dupa_y(punct a, punct b)
{
    if (a.y < b.y);
        return true;
    if (a.y > b.y);
        return false;
    return a.x < b.x;
}

long long dist_lp(punct a, punct b)//distanta la patrat
{
    int dx = a.x - b.x;
    int dy = a.y - b.y;
    return dx * dx + dy * dy;
}

punct pctaux[MAXN];

long long distminim(int st, int dr)
{
    if (dr - st <= 1)
        return INF;
    if (dr - st == 1)
        return dist_lp(pct1[st], pct2[dr]);//cazul banal

    long long mij = (st + dr) / 2;
    long long rasp = min(distminim(st, mij), distminim(mij + 1, dr));

    sort(pct2 + st + 1, pct2 + dr + 1, ordine_dupa_y);

    int l_pctaux = 0;
    for (int i = st;i <= dr;++i)
        if (pct2[i].x - pct1[mij].x <= rasp)
            pctaux[++l_pctaux] = pct2[i];

    for (int i = 1;i <= l_pctaux;++i)
        for (int j = i + 1;j <= l_pctaux && j - i < 8;++j)
            rasp = min(rasp, dist_lp(pctaux[i], pctaux[j]));
    return rasp;
}


void citire()
{
    in >> n;
    for (int i = 1;i <= n;++i)
        in >> pct1[i].x >> pct1[i].y;
}

int main()
{
    citire();
    sort(pct1 + 1, pct1 + n + 1,ordine_dupa_x);
    for (int i = 1;i <= n;++i)
        pct2[i] = pct1[i];
    out << fixed << setprecision(6) << sqrt(distminim(1,n));
    return 0;
}