Cod sursa(job #970626)

Utilizator BitOneSAlexandru BitOne Data 7 iulie 2013 14:47:01
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.53 kb
#include <cmath>
#include <vector>
#include <fstream>
#include <iomanip>
#include <iterator>
#include <algorithm>

namespace std
{
    inline istream& operator>>(istream& in, pair<int, int>& x)
    {
        in >> x.first >> x.second;
        return in;
    }
    inline ostream& operator<<(ostream& out, const pair<int, int>& x)
    {
        out << '(' << x.first << ", " << x.second << ')';
        return out;
    }
}
using namespace std;

typedef pair<int, int> point;

vector<point> Px, Py, aux;

inline double dist(const point& x, const point& y)
{
    return (x.first - y.first) * (x.first - y.first) +
           (x.second - y.second) * (x.second - y.second);
}
inline double min(const double& x, const double& y)
{
    return x - y < 1e-12 ? x : y;
}
inline bool cmpY(const point& x, const point& y)
{
    return (x.second < y.second) || (x.second == y.second && x.first < y.first);
}
inline void _swap(point& x, point& y) {point aux = x; x = y; y = aux;}

inline double closestPair(vector<point>& P, int left, int right)
{
    if(left >= right) return -1;
    if(right - left <= 10)
    {
        int i, j;
        double minim = dist(P[left], P[right]);
        for(i = left; i < right; ++i)
        {
            for(j = i + 1; j <= right; ++j)
            {
               minim = min(minim, dist(P[i], P[j])); 
               if(!cmpY(P[i], P[j]))
               {
                   _swap(P[i], P[j]);
               }
            }
        }
        return minim;
    }
    double minim;
    int middle = (left + right) >> 1, i, j, k;

    minim = min(closestPair(P, left, middle), closestPair(P, middle + 1, right));

    
    merge(P.begin() + left, P.begin() + middle + 1, 
          P.begin() + middle + 1, P.begin() + right + 1,
          aux.begin() + left, cmpY);
    copy(aux.begin() + left, aux.begin() + right + 1, P.begin() + left);
    
    for(i = j = left; i <= right; ++i)
    {
        if(dist(P[i], Px[middle + 1]) - minim < 1e-12)
        {
            aux[j++] = P[i];
        }
    }
    for(i = left; i < j; ++i)
    {
        for(k = 1; k <= 7 && i + k < j; ++k)
        {
            minim = min(minim, dist(aux[i], aux[i + k]));
        }
    }
    
    return minim;
}

int main()
{
    int N;
    ifstream in("cmap.in");
    ofstream out("cmap.out");
    
    in >> N;
    copy(istream_iterator<point>(in), istream_iterator<point>(), back_inserter(Px));
    Py = Px;
    aux.resize(Py.size());
    sort(Px.begin(), Px.end());
    
    out << setprecision(6) << fixed << sqrt(closestPair(Py, 0, Py.size() - 1)) << '\n';
    
    return EXIT_SUCCESS;
}