Cod sursa(job #1448184)

Utilizator dm1sevenDan Marius dm1seven Data 6 iunie 2015 13:59:40
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3.72 kb
/*
 * e_046_cm_apropiate_puncte.cpp
 *
 *  Created on: Jun 6, 2015
 *      Author: Marius
 */

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <utility>
using namespace std;

namespace e_046_cmap_nms
{
    typedef pair<int, int> Point;

    int N;
    vector<Point> points;

    double points_dist(Point& p1, Point& p2)
    {
        int x1 = p1.first, y1 = p1.second;
        int x2 = p2.first, y2 = p2.second;

        int dx = x1 - x2, dy = y1 - y2;
        return sqrt(dx * dx + dy * dy);
    }

    double join_min_dist_in_set(int a, int m, int b, double dist)
    {
        //build the set Y1
        vector<Point> Y1;
        int my1 = m;
        while (a <= my1 && points[m + 1].first - points[my1].first <= dist)
        {
            Point p1;
            p1.first = points[my1].second;
            p1.second = points[my1].first;
            Y1.push_back(p1);
            my1--;
        }

        //build the set Y2
        vector<Point> Y2;
        int my2 = m + 1;
        while (my2 <= b && points[my2].first - points[m].first <= dist)
        {
            Point p2;
            p2.first = points[my2].second;
            p2.second = points[my2].first;
            Y2.push_back(p2);
            my2++;
        }

        //sorts the sets Y1 and Y2
        std::sort(Y1.begin(), Y1.end());
        std::sort(Y2.begin(), Y2.end());

        // for each point in the set Y1, find the closest point in the set Y2, which should be 
        // smaller than the minimum distance computed so far
        int sz1 = Y1.size();
        int sz2 = Y2.size();
        double min_inter_dist = std::numeric_limits<double>::max();
        int i2_i1_start = 0;
        for (int i1 = 0; i1 < sz1; i1++)
        {
            int i2 = i2_i1_start;
            while (i2 < sz2 && points_dist(Y1[i1], Y2[i2]) >= dist)
                i2++;
            
            if (i2 < sz2) //we have found at least a point in Y2 such that dist(y1, y2) < dist
            {
                //save the new i2_i1_start
                i2_i1_start = i2;
                
                //start finding the minimum
                int i3 = i2;
                double dist13;
                while (i3 < sz2 && (dist13 = points_dist(Y1[i1], Y2[i3])) <= dist)
                {
                    min_inter_dist = min(min_inter_dist, dist13);
                    i3++;
                }
            }
        }
        
        return min(dist, min_inter_dist);
    }
    
    double min_dist_in_set(int a, int b)
    {
        if (b - a + 1 <= 3) //2 or 3 numbers; 1 not reachable by design
        {
            double min_dist = std::numeric_limits<double>::max();
            for (int i = a; i <= b; i++)
                for (int j = a; j <= b; j++)
                    if (j != i) min_dist = min(min_dist, points_dist(points[i], points[j]));
            return min_dist;
        }

        //otherwise
        //divide et impera
        int m = (a + b) / 2;
        double dist1 = min_dist_in_set(a, m);
        double dist2 = min_dist_in_set(m + 1, b);
        //join (impera)
        double dist_ = min(dist1, dist2);
        return join_min_dist_in_set(a, m, b, dist_);

    }
}

int main()
{
    using namespace e_046_cmap_nms;

    ifstream ifs("cmap.in");
    ifs >> N;
    points.resize(N);
    for (int i = 0; i < N; i++)
        ifs >> points[i].first >> points[i].second;
    ifs.close();

    //sort the points
    std::sort(points.begin(), points.end());

    double min_dist = min_dist_in_set(0, N - 1);

    ofstream ofs("cmap.out");
    ofs.precision(10);
    ofs << min_dist << endl;
    ofs.close();

    return 0;
}