Cod sursa(job #1448327)

Utilizator dm1sevenDan Marius dm1seven Data 6 iunie 2015 17:57:13
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 2.5 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 long long sll;
    typedef pair<sll, sll> Point;

    int N;
    vector<Point> X;
    vector<Point> Y;
    vector<Point> V;

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

        sll dx = x1 - x2, dy = y1 - y2;
        return dx * dx + dy * dy;
    }    

    sll min_dist_in_set(int a, int b, vector<Point>& Y)
    {
        if (b - a == 0) return std::numeric_limits<sll>::max();
        
        if (b - a == 1)
        {
            //also sort the the points in Y by the Y coordinates
            if (Y[a] > Y[b]) swap(Y[a], Y[b]);
            return points_dist(X[a], X[b]);
        }

        //otherwise
        //divide et impera
        int m = (a + b) / 2;
        sll dist1 = min_dist_in_set(a, m, Y);
        sll dist2 = min_dist_in_set(m + 1, b, Y);
        //join (impera)
        sll dist_ = min(dist1, dist2);
        //Y-sorted between a and m
        //Y-sorted between m+1 and b
        //should be interleaved between a and b
        //...but I'am lazy and I sort them again
        std::sort(Y.begin() + a, Y.begin() + b + 1);

        //find the elements in Y that are close to the vertical axis between x[m] and x[m+1]
        int vsize = 0;
        for (int i = a; i <= b; i++)
            if (abs(Y[i].second - X[m].first) <= dist_)
                V[vsize++] = Y[i];
                
        for (int i = 0; i < vsize; i++)
            for (int j = i + 1; j <= i + 7 && j < vsize; j++)
                dist_ = min(dist_, points_dist(V[i], V[j]));
        
        return dist_;
    }
}

int main()
{
    using namespace e_046_cmap_nms;

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

    //sort the points on the x-axis
    std::sort(X.begin(), X.end());
    
    sll min_dist = min_dist_in_set(0, N - 1, Y);

    ofstream ofs("cmap.out");
    ofs.precision(6);
    ofs << fixed;
    ofs << sqrt(min_dist + 0.0) << endl;
    ofs.close();

    return 0;
}