Cod sursa(job #1558376)

Utilizator akaprosAna Kapros akapros Data 29 decembrie 2015 00:39:55
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
#include <bits/stdc++.h>
#define mp make_pair
#define maxN 100002
#define f first
#define s second
#define ll long long
#define inf 4e18
using namespace std;
int n;
vector < pair < ll, ll > > V(maxN), x, y;
ll dist(const pair < ll, ll > &a, const pair < ll, ll > &b)
{
    return (a.f - b.f) * (a.f - b.f) + (a.s - b.s) * (a.s - b.s);
}
void read()
{
    int i;
    freopen("cmap.in", "r", stdin);
    scanf("%d", &n);
    x.resize(n); y.resize(n);
    for (i = 0; i < n; ++ i)
        scanf("%lld %lld", &x[i].f, &x[i].s);
    sort(x.begin(), x.end());
}
void solve()
{
    int i;
    for (i = 0; i < x.size(); ++ i)
        y[i] = mp(x[i].s, x[i].f);
}
ll sol(int l, int r, vector < pair < ll, ll > > &x, vector < pair < ll, ll > > &y)
{
    if (r - l <= 1)
       return inf;
    else
        if (r - l == 2)
    {
        if (y[l] > y[l + 1])
           swap(y[l], y[l + 1]);
        return dist(x[l], x[l + 1]);
    }
    int mid = (l + r) >> 1;
    ll bst = min(sol(l, mid, x, y), sol(mid, r, x, y));
    merge(y.begin() + l, y.begin() + mid, y.begin() + mid, y.begin() + r, V.begin());
    copy(V.begin(), V.begin() + (r - l), y.begin() + l);
    int len = 0, i, j;
    for (i = l; i < r; ++ i)
        if (abs(x[mid].f - y[i].s) <= bst)
           V[len ++] = y[i];
    for (i = 0; i < len - 1; ++ i)
        for (j = i + 1; j < len && j - i <= 7; ++ j)
            bst = min(bst, dist(V[i], V[j]));
    return bst;
}
void write()
{
    freopen("cmap.out", "w", stdout);
    printf("%.6lf", sqrt(sol(0, x.size(), x, y)));
}
int main()
{
    read();
    solve();
    write();
    return 0;
}