Cod sursa(job #1448372)

Utilizator dm1sevenDan Marius dm1seven Data 6 iunie 2015 21:01:47
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.9 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;
    vector<Point> S;

    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);
        //...but only 70 points
        //interleave        
        int i1 = a, i2 = m + 1;
        int k = a;
        while (i1 <= m && i2 <= b)
            if (Y[i1] <= Y[i2]) S[k++] = Y[i1++];
            else S[k++] = Y[i2++];
        while (i1 <= m) S[k++] = Y[i1++];
        while (i2 <= b) S[k++] = Y[i2++];
        
        //copy the elements back to Y
        for (int i = a; i <= b; i++) Y[i] = S[i];

        //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);
    S.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;
}