Cod sursa(job #2286761)

Utilizator HD650Stoicescu Adrian Nicolae HD650 Data 20 noiembrie 2018 18:09:16
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.74 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
using namespace std;
const int NMAX = 100001;
ifstream f("cmap.in");
ofstream g("cmap.out");
struct punct
{
    int x, y;
};

punct px[NMAX], py[NMAX], aux[NMAX];
int N;

bool compx(const punct &A, const punct &B)
{
    return A.x < B.x;
}

bool compy(const punct &A, const punct &B)
{
    return A.y < B.y;
}

long long dist2(const punct &A, const punct &B)
{
    return (A.x - B.x)*(A.x - B.x) + (A.y - B.y)*(A.y - B.y);
}

long long distMin(int p, int u)
{
    long long dmin = 0x7FFFFFFFFFFFFFFFLL;
    for(int i = p; i < u; i++)
        for(int j = i + 1; j <= u; j++)
        {
            long long dij = dist2(px[i], px[j]);
            if(dmin > dij)
                dmin = dij;
        }
    return dmin;
}

long long calcDmin(int p, int u)
{
    if(u - p < 3)
        return distMin(p, u);
    int m = (p + u) / 2;
    long long d1 = calcDmin(p, m);
    long long d2 = calcDmin(m, u);
    long long dd = min(d1, d2);
    sort(py + p, py + u + 1, compy);
    int k = 0;
    for(int i = p; i <= u; i++)
        if((py[i].x - px[m].x)*(py[i].x - px[m].x) < dd)
            aux[++k] = py[i];
    for(int i = 1; i < k; i++)
        for(int j = i + 1; j <= k && (aux[j].y - aux[i].y)*(aux[j].y - aux[i].y) < dd; j++)
        {
            d1 = dist2(aux[i], aux[j]);
            if(dd > d1)
                dd = d1;
        }
    return dd;
}

int main()
{
    f >> N;
    for(int i = 1; i <= N; i++)
        f >> px[i].x >> px[i].y;
    sort(px + 1, px + N + 1, compx);
    for(int i = 1; i <= N; i++)
        py[i] = px[i];
    g << fixed << setprecision(6) << sqrt(calcDmin(1, N));
    return 0;
}