Cod sursa(job #1662820)

Utilizator Vlad_317Vlad Panait Vlad_317 Data 25 martie 2016 09:41:27
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.74 kb
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;

const int MAX = 100001;
const long long INF = 2000000000000000000LL;

struct puncte
{
    int x, y;
}v[MAX], aux[MAX];

long long dist(puncte a, puncte b)
{
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

long long modul(long long a)
{
    if(a < 0)
        return -a;
    return a;
}

bool cmpx(puncte a, puncte b)
{
    return a.x < b.x;
}

long long compute(int st, int dr, long long d)
{
    int nr, m = (st + dr) / 2, i, j, k, lim;
    puncte mij = v[m];
    i = k = st;
    j = m + 1;
    while (i <= m && j <= dr)
        if (v[i].y <= v[j].y)
            aux[k++] = v[i++];
        else
            aux[k++] = v[j++];
    while (i <= m)
        aux[k++] = v[i++];
    while (j <= dr)
        aux[k++] = v[j++];

    nr = 0;
    for (i = st; i <= dr; i++)
    {
        v[i] = aux[i];
        if (modul(v[i].x - mij.x) <= d)
            aux[nr++] = aux[i];
    }

    for (i = 0; i + 1 < nr; i++)
    {
        lim = i + 8;
        if (lim > nr)
            lim = nr;
        for (j = i + 1; j < lim; j++)
            d = min(d, dist(aux[i], aux[j]));
    }
    return d;

}

long long divide(int left, int right)
{
    if(left == right)
        return INF;

    int mid = (right + left)/2;
    long long d1 = divide(left, mid);
    long long d2 = divide(mid + 1, right);
    long long delta = min(d1, d2);
    return compute(left, right, delta);
}

int main()
{
    FILE *fin, *fout;


    fin = fopen("cmap.in", "r");
    fout = fopen("cmap.out", "w");

    int n;

    fscanf(fin, "%d", &n);

    for(int i = 0; i < n; i++)
        fscanf(fin, "%d %d", &v[i].x, &v[i].y);

    sort(v, v + n, cmpx);

    fprintf(fout, "%.6f", sqrt(divide(0, n - 1)));

    return 0;
}