Cod sursa(job #1041699)

Utilizator TripluYOlteanu Costin TripluY Data 26 noiembrie 2013 00:02:07
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3.76 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;
struct punct
{
    long x;
    long y;
};

bool punct_cmp(punct prim,punct doilea)
{
    return (prim.x < doilea.x);
}

long maxim;

int n;
punct *vector_puncte;
punct *vector2_puncte;

inline double distanta(punct primul, punct doilea)
{
    return sqrt((double)(primul.x - doilea.x)*(primul.x - doilea.x) + (double)(primul.y - doilea.y)*(primul.y - doilea.y));
}

inline void combina(punct *de_combinat,int primul, int ultimul)
{
    const int mijloc = (primul + ultimul) / 2;
    int set_1_start = primul;
    int set_1_final = mijloc;
    int set_2_start = mijloc+1;
    int set_2_final = ultimul;

    vector<punct>ordonat;
    ordonat.reserve(ultimul - primul);

    while (set_1_start <= set_1_final && set_2_start <=set_2_final)
    {
        if (de_combinat[set_1_start].y < de_combinat[set_2_start].y)
        {
            ordonat.push_back(de_combinat[set_1_start]);
            ++set_1_start;
        }
        else
        {
            ordonat.push_back(de_combinat[set_2_start]);
            ++set_2_start;
        }
    }

    while (set_1_start <= set_1_final)
    {
        ordonat.push_back(de_combinat[set_1_start]);
        ++set_1_start;
    }

    while (set_2_start <= set_2_final)
    {
        ordonat.push_back(de_combinat[set_2_start]);
        ++set_2_start;
    }

    int j = 0;
    for(vector<punct>::iterator it = ordonat.begin();it != ordonat.end();++it)
    {
        de_combinat[primul + j] = *it;
        ++j;
    }
}

double distanta_minima(int primul, int ultimul)
{
    if (primul == ultimul)
        return maxim;
    if (ultimul == primul + 1)
    {
        if (vector2_puncte[primul].y > vector2_puncte[ultimul].y)
            swap(vector2_puncte[primul], vector2_puncte[ultimul]);
        return distanta(vector2_puncte[primul], vector2_puncte[ultimul]);
    }
    if(ultimul == primul + 2)
    {
        if(vector2_puncte[primul + 1].y < vector2_puncte[primul].y)
        if(vector2_puncte[primul + 1].y < vector2_puncte[primul].y)
            swap(vector2_puncte[primul],vector2_puncte[primul + 1]);
        if(vector2_puncte[ultimul].y < vector2_puncte[ultimul - 1].y)
            swap(vector2_puncte[ultimul],vector2_puncte[ultimul - 1]);
        return min(min(distanta(vector2_puncte[primul],vector2_puncte[primul + 1]),distanta(vector2_puncte[primul],vector2_puncte[ultimul])),distanta(vector2_puncte[ultimul - 1],vector2_puncte[ultimul]));
    }

    combina(vector2_puncte,primul, ultimul);

    int mijloc = (primul + ultimul)/2;
    double distanta_min = min(distanta_minima(primul, mijloc), distanta_minima(mijloc + 1, ultimul));

    punct *curent = new punct[ultimul - primul + 1];
    int k = 0;

    for (int i=primul; i<=ultimul; i++)
        if (abs(vector2_puncte[i].x - vector_puncte[mijloc].x) <= (long)distanta_min)
        {
            curent[k] = vector2_puncte[i];
            ++k;
        }

    for (int i=0; i<k; i++)
        for (int j = i+1; j <= i+7 && j < k; j++)
            if (distanta(curent[i], curent[j]) < distanta_min)
                distanta_min = distanta(curent[i], curent[j]);

    return distanta_min;
}

int main()
{
    ifstream f("cmap.in");
    f>>n;
    vector_puncte = new punct[n];
    vector2_puncte = new punct[n];
    for (int i=0; i < n; i++)
    {
        f>>vector_puncte[i].x;
        f>>vector_puncte[i].y;
    }
    f.close();

    maxim = distanta(vector_puncte[0],vector_puncte[1]);

    sort(vector_puncte,vector_puncte+n,punct_cmp);

    for (int i=0; i < n; i++)
        vector2_puncte[i] = vector_puncte[i];

    ofstream g("cmap.out");
    g<<distanta_minima(0, --n);
    g.close();

    return 0;
}