Cod sursa(job #1510160)

Utilizator sebinechitasebi nechita sebinechita Data 24 octombrie 2015 16:59:16
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
#define MAX 100100
int minim = 0;
long long d = (1ll<<60);
pair<int, int> a[MAX], b[MAX];

long long 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);
}

long long de(int st, int dr)
{
    int i, j;
    if(st == dr)
        return (1ll<<60);
    if(st + 1 == dr)
    {
        if(a[st] > a[dr])
            swap(a[st], a[dr]);
        return dist(a[st], a[dr]);
    }
    int mij = (st + dr) >> 1;
    d = min(min(d, de(st, mij)), de(mij + 1, dr));
    int di = a[mij].second;
    merge(a + st, a + mij + 1, a + mij + 1, a + dr + 1, b + 1);
    int dr2 = 0;
    for(i = 1 ; i <= dr - st + 1 ; i++)
    {
        a[st + i - 1] = b[i];
        if(b[i].second + d >= di && b[i].second - d <= di)
            b[++dr2] = b[i];
    }
    for(i = 1 ; i <= dr2 ; i++)
        for(j = i + 1 ; d >= 1LL*(b[j].first - b[i].first)*(b[j].first - b[i].first) && j <= dr2; j++)
        {
            minim = max(minim, j - i + 1);
            d = min(d, dist(b[i], b[j]));
        }
    return d;
}


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 << fixed << setprecision(6) << sqrt(1.0 * de(1, n)) << '\n';
   // cout << minim << "\n";
}