Cod sursa(job #807305)

Utilizator psycho21rAbabab psycho21r Data 4 noiembrie 2012 16:07:40
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <fstream>
#include <vector>
#include <utility>
#include <algorithm>
#include <math.h>

using namespace std;

class plane
{
    vector<pair<int, int> > points;
    public:
        void add_point(int x, int y)
        {
            points.push_back(make_pair(x, y));
        }
        void sort_points()
        {
            sort(points.begin(), points.end());
        }
        double distance_between_closest_points()
        {
            return tpdist(0, points.size() - 1);
        }
    private:
        double tpdist(int left, int right)
        {
            double d = (10 << 11) + 11;
            for(int i = 0; i < points.size(); ++i)
            {
                for(int j = i + 1; j <= i + 7 && j < points.size(); ++j)
                {
                    double run = points[j].first - points[i].first;
                    double rise = points[j].second - points[i].second;
                    double dist = sqrt((double)pow(run, 2) + (double)pow(rise, 2));
                    if(dist < d)
                        d = dist;
                }
            }
            return d;
        }
};

int main()
{
    ifstream in("cmap.in");
    ofstream out("cmap.out");
    int N;
    in >> N;
    plane P;
    for(int i = 0, x, y; i < N; ++i)
    {
        in >> x >> y;
        P.add_point(x, y);
    }
    P.sort_points();
    out.precision(8);
    out << P.distance_between_closest_points();



    return 0;
}