Cod sursa(job #2046867)

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

using namespace std;

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

int N;
const ll INF = unsigned(-1);
pair <ll, ll> A[NMAX], V[NMAX];

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

long long solve(int st, int dr) {
    ll p, p1, p2;
    if (dr-st == 1) {
        return INF;
    }
    if (dr-st == 2) {
        p = euclid(A[st], A[dr]);
        return p;
    } else if (dr-st == 3) {
        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);
    ll e = A[mid].x;
    int k = 0;
    for(int i = st; i <= dr; ++i) {
        if(abs(A[i].y - e) <= p) {
            V[++k] = A[i];
        }
    }
    for(int i = 1; i <= k; ++i) {
        for(int j = i + 1; j <= k and j < 8; ++j) {
            p = min(p, euclid(V[i],V[j]));
        }
    }
    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;
}