Cod sursa(job #2352805)

Utilizator oanceadavidOancea David oanceadavid Data 23 februarie 2019 17:54:05
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.82 kb
#include <bits/stdc++.h>

using namespace std;

unsigned long long distanta (const pair<int, int>& point_a, const pair<int, int>& point_b)
{
    return  ( (unsigned long long)(point_a.first - point_b.first) * (unsigned long long)(point_a.first - point_b.first)
              + (unsigned long long)(point_a.second - point_b.second) * (unsigned long long)(point_a.second - point_b.second));
}

int number_of_points (int left, int right)
{
    return left - right + 1;
}

unsigned long long cmap (const vector< pair<int, int> >& points, int left, int right)
{
    if (number_of_points (left, right) <= 3)
    {
        unsigned long long mini = numeric_limits<unsigned long long>::max();
        for (int i = left; i < right; i++)
        {
            for (int j = i + 1; j <= right; j++)
            {
                mini = min (mini, distanta (points[i], points[j]));
            }
        }
        return mini;
    }
    int midIdx = (right+left)/2;
    unsigned long long mini = min(cmap(points,left,midIdx),cmap(points,midIdx+1,right));
    int i,j;
    i=midIdx;
    j=midIdx;
    int prev_x = points[midIdx - 1].first;
    int succ_x = points[midIdx + 1].first;
    while(points[i].first == prev_x) i--;
    i++;
    while(points[j].first == succ_x) j++;
    j--;

    for(int k = i; k < j-1; k++)
    {
        for(int l = k+1; l < j; l++)
        {
            mini = min(mini, distanta(points[k],points[l]));
        }
    }

    return mini;
}

int main()
{
    int n;
    ifstream in("cmap.in");
    ofstream out("cmap.out");
    in.tie(NULL);
    ios::sync_with_stdio(false);
    in >> n;
    vector< pair<int, int> > points (n);
    for (int i = 0; i < n; i++)
    {
        in >> points[i].first >> points[i].second;
    }
    sort (begin (points), end (points));
    out <<fixed<<setprecision(6) << sqrt(cmap (points, 0, n - 1));
    return 0;
}