Cod sursa(job #808717)

Utilizator psycho21rAbabab psycho21r Data 7 noiembrie 2012 10:31:25
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.07 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
#define INF 1000000000

using namespace std;

class plane
{
    private:
        vector<pair<int, int> > points;
    public:
        void push(int x, int y)
        {
            points.push_back(make_pair(x, y));
        }
        float distance_between_closest_points()
        {
            sort(points.begin(), points.end());
            return cpd(0, points.size() - 1);
        }
    private:
        float distance(pair<int, int>a, pair<int, int> b)
        {
            return sqrt(pow(b.first - a.first, 2) + (float)pow(b.second - a.second, 2));
        }
        float cpd(int left, int right)
        {
            int mid = (left + right)/2;
            if(left == right)
                return INF;
            if(right - left == 1)
                return distance(points[left], points[right]);

            float min_left = cpd(left, mid);
            float min_right = cpd(mid + 1, right);
            float min_sides = min(min_left, min_right);
            for(int i = mid; i >= 0 && points[i].first > points[mid].first - min_sides; --i)
            {
                for(int j = mid; j < points.size() && points[j].first < points[mid].first + min_sides; ++j)
                {
                    if(points[j].second < points[i].second + min_sides && points[i].second - min_sides < points[j].second)
                    {
                        float temp_dis = distance(points[i], points[j]);
                        if(temp_dis > min_sides)
                            min_sides = temp_dis;
                    }
                }
            }
            return min_sides;
        }


};

int main()
{
    ifstream in("cmap.in");
    ofstream out("cmap.out");

    plane my_plane;
    int N;
    in >> N;
    for(int i = 0, x, y; i < N; ++i)
    {
        in >> x >> y;
        my_plane.push(x, y);
    }

    out.precision(1000);
    out << my_plane.distance_between_closest_points();

    in.close();
    out.close();
}