Cod sursa(job #1515700)

Utilizator mirupetPetcan Miruna mirupet Data 2 noiembrie 2015 08:32:45
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include<cstdio>
#include<fstream>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<cmath>
#define DIM 100002
#define INF (1LL << 60)
#define Minim(x, y) (x <= y ? x : y)
using namespace std;

int N;
vector < pair<int, int> > v;
pair <int, int> w[DIM];
int NR;

inline long long dist(const pair <int, int>& a, const pair <int, int>& b)
{
    return 1LL * (a.first - b.first) * (a.first - b.first) + 1LL * (a.second - b.second) * (a.second - b.second);
}
long long Solve (int, int);

int main()
    {
        ifstream f("cmap.in");
        ofstream g("cmap.out");

        f >> N;

        for (int i = 1; i <= N; ++i)
        {
            v.push_back(make_pair(0, 0));
            f >> v.back().first >> v.back().second;
        }

        sort (v.begin(), v.end());

        g << fixed << setprecision(7) << sqrt(1.0L * Solve(0, int(v.size()) - 1)) << '\n';
    }

long long Solve(int left, int right)
{
    if (left == right)
        return INF;
    if (right - left == 1)
        return dist(v[left], v[right]);

    int mid = (left + right) >> 1;

    int X = v[mid].first;
    long long d1 = Solve(left, mid), d2 = Solve(mid + 1, right);
    long long dmin = Minim(d1, d2);

    NR = 0;
    for (int i = left; i <= right; ++i)
        if (v[i].first >= X - dmin && v[i].first <= X + dmin)
            w[++NR] = make_pair(v[i].second, v[i].first);
    sort (w + 1, w + NR + 1);

    for (int i = 1; i <= NR; ++i)
        for (int j = 1; i + j <= NR && j <= 7; ++j)
            dmin = Minim(dmin, dist(w[i], w[i + j]));

    return dmin;
}