Cod sursa(job #2519444)

Utilizator DanielSim24Daniel Simionov DanielSim24 Data 7 ianuarie 2020 19:16:51
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.46 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <math.h>
using namespace std;

struct PUNCT
{
    double x, y;
};

#define NMAX 99999
PUNCT p[NMAX], aux[NMAX], inter[NMAX], A, B;

double distanta(PUNCT a, PUNCT b)//distanta dintre doua puncte din plan
{
    return sqrt((b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y));
}

bool cmpX(PUNCT a, PUNCT b) //sortare dup X
{
    return a.x < b.x;
}

bool cmpY(PUNCT a, PUNCT b) //sortare dupa Y
{
    return a.y < b.y;
}

double dist_min(int left, int right)
{
    if(right - left + 1 == 3) //avem 3 puncte de o parte a medianei
    {
        sort(p + left, p + right, cmpY); //sortare dupa Y
        double d1 = distanta(p[left], p[left + 1]);
        double d2 = distanta(p[left + 1], p[left + 2]);
        double d3 = distanta(p[left], p[left + 2]);
        double minim = d1;
        A = p[left];
        B = p[left + 1];
        if(d2 < minim) //aflam care sunt cele 2 puncte cele mai apropiate
        {
           minim = d2;
           A = p[left + 1];
           B = p[left + 2];
        }
        if(d3 < minim)
        {
            A = p[left];
            B = p[left + 2];
            minim = d3;
        }
        return minim;
    }
    if(right - left + 1 == 2) //avem doar 2 puncte de o parte a medianei
    {
        if(p[left].y > p[left + 1].y) //crescator
            swap(p[left], p[left + 1]);
        A = p[left];
        B = p[left + 1];
        return distanta(p[left], p[left + 1]);
    }
    else
    {
        int mijloc = (left + right) / 2; //impartim multimea de puncte a.i. sa avem n/2 puncte de fiecare parte
        double mediana = p[mijloc].x;
        double delta = min(dist_min(left, mijloc), dist_min(mijloc + 1, right));//apelam functia recursiv, pentru a imparti in subprobleme cat mai mici
        int nr = 0, i, j, k;

        //sortam prin interclasare(dupa valoarea ordonatei, y) punctele aflate de ambele parti ale medianei
        i = left;
        k = left;
        j = mijloc + 1;
        while(i <= mijloc && j <= right)
            if(p[i].y < p[j].y)
                aux[k++] = p[i++];
            else aux[k++] = p[j++];
        while(i <= mijloc)
            aux[k++] = p[i++];
        while(j <= right)
            aux[k++] = p[j++];

        for(i = left; i <= right; i++)
        {
            p[i] = aux[i];
            if(p[i].x - mediana <= delta && p[i].x - mediana >= -delta) // [-delta, delta]
                    inter[++nr] = p[i]; //selectam doar punctele care se afla la o distanta de cel mult delta fata de mediana trasata
        }

        for(i = 1; i <= nr; i++)
        {
            int nr_vecini = min(nr, i + 7); //stim ca este suficient sa verificam cu urmatorii 7 vecini
            for(j = i + 1; j <= nr_vecini; j++)
                    if(distanta(inter[i], inter[j]) < delta) //verificam daca avem 2 puncte care sa ofere o noua distanta minima
                    {
                        delta = distanta(inter[i],inter[j]);
                        A = inter[i];
                        B = inter[j];
                    }
        }
        return delta;
    }
}

int main()
{
    ifstream fin("cmap.in");
    ofstream fout("cmap.out");
    int n, i;
    fin >> n;
    for(i = 1; i <= n; i++)
        fin >> p[i].x >> p[i].y;
    sort(p + 1 , p + n + 1, cmpX); //sortare dupa X
    fout << setprecision(6) << fixed << dist_min(1, n);
    return 0;
}