Cod sursa(job #2046851)

Utilizator PletoPletosu Cosmin-Andrei Pleto Data 24 octombrie 2017 10:16:00
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <bits/stdc++.h>
#define NMAX 100010
#define x first
#define y second

using namespace std;

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

int N;
pair <int, int> A[NMAX], V[NMAX];

inline int euclid(pair <int, int> a, pair <int, int> b) {
    return (b.y-a.y)*(b.y-a.y) + (b.x-a.x)*(b.x-a.x);
}

int solve(int st, int dr) {
    int p, p1, p2;
    if (dr-st == 1) {
        p = euclid(A[st], A[dr]);
        return p;
    } else if (dr-st == 2) {
        p = min(euclid(A[st], A[st+1]), euclid(A[st+1], A[st+2]));
        p = min(p2, euclid(A[st], A[st+2]));
        return p;
    }
    int mid = (st+dr)/2;
    p1 = solve(st, mid);
    p2 = solve(mid+1, dr);
    p = min(p1, p2);
    int e = A[mid].x;
    int k = 0;
    for(int i = st; i <= dr; ++i) {
        if(abs(A[i].x - e) <= p) {
            V[++k] = A[i];
        }
    }
    for(int i = 1; i <= k; ++i) {
        for(int j = i + 1; j <= k and j <= 8; ++j) {
            int euc = euclid(V[i],V[j]);
            p = min(p, euc);
        }
    }
    return p;
}

int main()
{
    fin>>N;
    for(int i = 1; i <= N; ++i) {
        fin>>A[i].x>>A[i].y;
    }
    sort(A+1, A+N+1);
    fout<<fixed<<setprecision(6)<<sqrt(solve(1, N));
    return 0;
}