Cod sursa(job #1244062)

Utilizator sebinechitasebi nechita sebinechita Data 16 octombrie 2014 18:59:41
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.76 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;

ifstream fin("cmap.in");
ofstream fout("cmap.out");
#define MAX 100010
#define INF (1LL<<60)
pair<int, int> a[MAX], b[MAX], c[MAX];

long long d(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 rez(int st, int dr)
{
    //cout << st << " " << dr << "{" << "\n";
    if(st==dr)
    {
     //   cout << 1LL*INF << "\n";
     //   cout << st << " " << dr << "}" << "\n";

        return INF;
    }
    if(st+1==dr)
    {
      //  cout<<d(a[st], a[dr])<<"\n";
      //  cout << st << " " << dr << "}" << "\n";

        return d(a[st], a[dr]);
    }
    int mid=(st+dr)>>1, i , j;
    int val=a[mid].second;
    long long di=min(rez(st, mid), rez(mid+1, dr));

    merge(a+st, a+mid+1, a+mid+1, a+dr+1, b);
    int v=0;
    for(i=0;i<dr-st+1;i++)
    {
        if(b[i].second>=val-di && b[i].first<=val+di)
        {
            c[++v]=b[i];
        }
    }
   // cout<<di<<" ";
    for(i=1;i<=v;i++)
    {
    //    cout<<di<<" ";
        for(j=1;j<=7 && c[i].first-c[i+j].first<=di && i+j<=v;j++)
        {
            di=min(di, d(c[i], c[i+j]));
        }
    }
    //cout<< di << "\n";
   // cout << st << " " << dr << "}" << "\n";

    return di;
}


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++)
    {
     //   cout << a[i].first << " " << a[i].second << "\n";
        swap(a[i].first, a[i].second);
    }
    //cout << "\n";
    fout << setprecision(7) << fixed << sqrt(1.0*rez(1, n)) ;
}