Cod sursa(job #2491456)

Utilizator andreibudoiAndrei Budoi andreibudoi Data 12 noiembrie 2019 17:10:51
Problema Cele mai apropiate puncte din plan Scor 0
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <cmath>
using namespace std;
 
ifstream f("cmap.in");
ofstream g("cmap.out");
 
pair <long long, long long> v[100001];
vector <pair <long long, long long> > aux;
 
long long dist(long long x1, long long x2, long long y1, long long y2)
{
    return  (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}
 
long long distDouaPuncte(int x, int y)
{
    return dist( v[x].first, v[y].first, v[x].second, v[y].second );
}
 
long long DEI(int st, int dr)
{
    if( dr - st <=3 )
    {
        long long d = distDouaPuncte(0,1);
        if( dr - st ==3 )
        {
            d = min( d, distDouaPuncte(1,2) );
            d = min( d, distDouaPuncte(0,2) );
        }
        return d;
    }
 
    long long med = st + (dr - st)/2;
    long long d = min( DEI(st, med), DEI(med, dr) );
 
    for(unsigned int i=0;i<aux.size();i++)
    {
        for(unsigned int j=i+1; j<i+8 && j<aux.size() ;j++)
        {
            d = min(d, dist(aux[i].first ,aux[j].first, aux[i].second, aux[j].second));
        }
    }
    return d;
}
 
int main()
{
    int n;
    f>>n;
    for(int i=0;i<n;i++)
        {
            f>>v[i].first>>v[i].second;
            aux.emplace_back(v[i].second,v[i].first);
        }
 
     sort(v, v+n);
 
     sort(aux.begin(),aux.end());
 
 
     g<<fixed<< setprecision(6) << sqrt (DEI(0, n));
    return 0;
}