Cod sursa(job #1401961)

Utilizator VictoriaNevTascau Victoria VictoriaNev Data 26 martie 2015 11:22:06
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 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;
pair<ll,ll> vicx, vicy;
pair<ll,ll> sp[NMAX], p1[NMAX], p2[NMAX];
inline 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(dr-st<=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-st)/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];
    m--;
    for(i=0; i<m; i++)
        for(j=i+1; j<=m&&j-i<=7; j++)
        {
            ans=min(ans,dist(sp[i],sp[j]));
            //vicx=sp[i];
            //vicy=sp[j];
        }
    return ans;
}
int main()
{
    ifstream in("cmap.in");
    ofstream out("cmap.out");
    in>>n;
    for(i=0; i<n; i++)
    in>>p1[i].first>>p1[i].second;
    sort(p1,p1+n);
    for(i=0; i<n; i++)
        p2[i]=make_pair(p1[i].second,p1[i].first);
    out<<setprecision(6)<<fixed<<sqrt(divide_et_impera(0,n))<<'\n';
    //out<<vicx.first<<' '<<vicx.second<<"    "<<vicy.first<<' '<<vicy.second<<'\n';
    return 0;
}