Cod sursa(job #1893377)

Utilizator CiurezAndreiCiurez Marius-Andrei CiurezAndrei Data 25 februarie 2017 17:33:52
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.79 kb
#include <bits/stdc++.h>

#define INF 200000000000

using namespace std;

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

int N;
pair<long long, long long> X[100010], Y[100010], v[100010];

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

inline long long closestPoints(int left, int right, pair<long long, long long> X[100010], pair<long long, long long> Y[100010])
{
    if(left >= right - 1) // sunt mai putin de 3 puncte
        return INF;

    if(right - left == 2)
    {
        if(Y[left] > Y[left + 1])
            swap(Y[left], Y[left + 1]);

        return dist(X[left], X[left + 1]);
    }

    int middle = (left + right) >> 1;
    long long solution = min( closestPoints(left, middle, X, Y), closestPoints(middle, right, X, Y) );

    sort(Y + left + 1, Y + right + 1); // sortam punctele dupa y din patratul actual

    int k = 0;
    for(int i = left; i < right; i ++)
    {
        if( abs(Y[i].second - X[middle].first) <= solution) // diferenta x-lor mai mica ca solution
        {
            v[++k] = Y[i];
        }
    }

    for(int i = 1; i < k; i ++)
    {
        for(int j = i + 1; j <= k && j - i < 8; j ++)
        {
            solution = min(solution, dist(v[i], v[j]));
        }
    }

    return solution;

}

int main()
{
    fin >> N;

    for(int i = 1; i <= N; i ++)
    {
        fin >> X[i].first >> X[i].second;
    }

    sort(X + 1, X + N + 1);

    for(int i = 1; i <= N; i ++)
    {
        Y[i] = make_pair(X[i].second, X[i].first); // le pun pe dos ca ma intereseaza y primu
    }

    fout << setprecision(6) << fixed << sqrt( closestPoints(0, N, X, Y) );

    return 0;
}