Cod sursa(job #1828903)

Utilizator japjappedulapPotra Vlad japjappedulap Data 14 decembrie 2016 00:58:58
Problema Cele mai apropiate puncte din plan Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.99 kb
#include <algorithm>
#include <bitset>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <cstdlib>
using namespace std;


//#include <iostream>
#include <fstream>
ifstream fin ("cmap.in");
ofstream cout ("cmap.out");

const int INF = 2000000000;
const int Nmax = 100000 + 10;
const double EPS = 0.000001;
using int64 = long long;
using PointTemp = pair <int64, int64>;

int N;
vector <PointTemp> P;
PointTemp C[Nmax], Aux[Nmax];


void Input();
inline int64 Dist(const PointTemp&, const PointTemp&);
inline int64 Solve(int64, int64);

int main()
{
    Input();
    sort(P.begin(), P.end());
    for (int i = 0; i < N; ++i)
        swap(P[i].first, P[i].second);
    cout << fixed << setprecision(6) << sqrt(1.0 * Solve(0, N-1));
};

inline int64 Solve(int64 Left, int64 Right)
{
    //cout << Left << ' ' << Right << '\n';
    if (Right - Left + 1 < 2)  return INF;
    if (Right - Left + 1 == 2) return Dist(P[Left], P[Right]);

    int Mid = (Left + Right) / 2;

    int DX = P[Mid].first;

    int64 d1 = Solve(Left, Mid), d2 = Solve(Mid+1, Right);
    int64 Best = min(d1, d2);

    merge(P.begin() + Left, P.begin() + Mid + 1, P.begin() + Mid + 1, P.begin() + Right + 1, Aux);

    int sz = 0;
    for (int i = 0; i < Right - Left + 1; ++i)
        if (Aux[i].second >= DX - Best && Aux[i].second <= DX + Best)
            C[++sz] = Aux[i];

    for (int i = 1; i <= sz; ++i)
        for (int j = 1; j + i <= sz && j <=7 ; ++j)
            Best = min(Best, Dist(C[i], C[i+j]));

    return Best;
};









void Input()
{
    fin >> N;
    for (int i = 1, x, y; i <= N; ++i)
    {
        fin >> x >> y;
        P.push_back({x, y});
    }
};





inline int64 Dist(const PointTemp& A, const PointTemp& B)
{
    return 1LL * (B.second - A.second) * (B.second - A.second) +  1LL * (B.first - A.first) * (B.first - A.first);
};