Cod sursa(job #1360875)

Utilizator danalex97Dan H Alexandru danalex97 Data 25 februarie 2015 18:31:01
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <iostream>
#include <iomanip>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

ifstream F("cmap.in");
ofstream G("cmap.out");

const int N = 100010;

int n;
pair<int,int> a[N];

double dist(pair<int,int> a,pair<int,int> b)
{
    return sqrt( 1LL*(a.first-b.first)*(a.first-b.first) + 1LL*(a.second-b.second)*(a.second-b.second) );
}

bool cmp(pair<int,int> a,pair<int,int> b)
{
    return a.second < b.second || ( a.second == b.second && a.first <= b.first );
}

double solve(int l,int r)
{
    if ( l == r ) return 1<<30;
    if ( r == l+1 ) return dist(a[l],a[r]);

    int m = (l + r) / 2;
    double ans = min( solve(l,m),solve(m+1,r) );

    int x = a[m].first;

    vector< pair<int,int> > pt;
    for (int i=l;i<=r;++i)
        if ( max(a[i].first-a[m].first,a[m].first-a[i].first) <= ans )
            pt.push_back( a[i] );
    sort(pt.begin(),pt.end(),cmp);

    for (int i=0;i<int(pt.size());++i)
        for (int j=1;j<=7;++j)
            if ( i+j < int(pt.size()) )
                ans = min(ans,dist(pt[i],pt[i+j]));

    return ans;
}

int main()
{
    F>>n;
    for (int i=1;i<=n;++i)
        F>>a[i].first>>a[i].second;
    sort(a+1,a+n+1);
    G<<fixed<<setprecision(6)<<solve(1,n)<<'\n';
}