Cod sursa(job #1415192)

Utilizator marcelPFake name marcelP Data 3 aprilie 2015 21:35:10
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
#define INF (~(1LL<<63))
#define MAX 100010
typedef long long ll;
ll dist(pair<int, int> A, pair<int, int> B)
{
    return 1LL * (A.first - B.first) * (A.first - B.first) + 1LL * (A.second - B.second) * (A.second - B.second);
}

pair<int, int> a[MAX], b[MAX], c[MAX];


ll rez(int st, int dr)
{
    if(st == dr)
        return INF;
    if(st == dr - 1)
        return dist(a[st], a[dr]);
    int mij = (st + dr) / 2;
    int dreapta = a[mij].second;
    ll val = min(rez(st, mij), rez(mij + 1, dr));
    merge(a + st, a + mij + 1, a + mij + 1, a + dr + 1, b);
    int x = 0;
    for(int i = 0 ; i <= dr - st ; i++)
    {
        if(1LL * (b[i].second - dreapta) * (b[i].second - dreapta) <= val)
        {
            c[++x] = b[i];

        }
        a[i + st] = b[i];
    }
    for(int i = 1 ; i <= x ; i++)
    {
        for(int j = 1 ; j <= 7 && i + j <= x; j++)
        {
            val = min(val, dist(c[i], c[i + j]));
        }
    }
    return val;
}

int main()
{
    int n, i;
    fin >> n;
    for(i = 1 ; i <= n ; i++)
    {
        fin >> a[i].first >> a[i].second;
    }
    sort(a + 1, a + n + 1);
    for(i = 1 ; i <= n ; i++)
    {
        swap(a[i].first, a[i].second);
    }
    fout << setprecision(6) << fixed << sqrt(1LL * rez(1, n)) << "\n";
}