Cod sursa(job #1401854)

Utilizator VictoriaNevTascau Victoria VictoriaNev Data 26 martie 2015 10:22:58
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
const int NMAX=100005;
typedef long long ll;
int n, i;
vector< pair<ll,ll> > sp(NMAX), p1, p2;
ll dist(const pair<ll,ll>& a,const pair<ll,ll>& b)
{
    return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second);
}
ll divide_et_impera(int st,int dr)
{
    if(st-dr>=-1)
        return 1LL<<60;
    if(dr-st==2)
    {
        if(p2[st]>p2[st+1])
            swap(p2[st],p2[st+1]);
        return dist(p1[st],p1[st+1]);
    }
    int med=(st+dr)/2;
    ll ans=min(divide_et_impera(st,med),divide_et_impera(med,dr));
    int m=0, i, j;
    for(i=st; i<=dr; i++)
        if(abs(p2[i].second-p1[med].first)<=ans)
            sp[++m]=p2[i];
    for(i=1; i<=m; i++)
        for(j=i+1; j<m&&j-i==7; j++)
            ans=min(ans,dist(sp[i],sp[j]));
    return ans;
}
int main()
{
    ifstream in("cmap.in");
    ofstream out("cmap.out");
    in>>n;
    p1.resize(n);
    p2.resize(n);
    for(i=0; i<p1.size(); i++)
        in>>p1[i].first>>p1[i].second;
    sort(p1.begin(),p1.end());
    for(i=0; i<p1.size(); i++)
        p2[i]=make_pair(p1[i].second,p1[i].first);
    out<<setprecision(6)<<fixed<<sqrt(divide_et_impera(0,n))<<'\n';
    return 0;
}