Cod sursa(job #2100643)

Utilizator ShrimpCalin Popescu Shrimp Data 5 ianuarie 2018 22:41:30
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.88 kb
#include<iostream>
#include<fstream>
#include<cmath>
#include<algorithm>
#include<iomanip>
using namespace std;

ifstream f("cmap.in");
ofstream g("cmap.out");


struct punct
{
    int x, y;
} *X,*Y,*LY;          /// in X si Y punctele , in LY punctele la distanta <= d fata de dreapta verticala

int n;

bool cmpX(punct a, punct b)
{
    return a.x < b.x;
}
bool cmpY(punct a, punct b)
{
    return a.y < b.y;
}

long long dist( punct a, punct b)
{
    long long X = 1LL * (a.x - b.x );
    long long Y = 1LL * ( a.y - b.y );
    return  X*X + Y*Y ;         /// calculeaza distanta euclidiana la patrat
}

long long divide(int st,int dr,punct y[],int nr)
{
    if(dr-st == 1)
        return dist( X[st], X[dr] );
    if (dr-st == 2)
        return min(dist(X[st], X[st+1]),min(dist(X[st+1], X[dr]),dist(X[st], X[dr])));
    int mij=(st+dr)/2;
    int i,p=0,q=0;
    punct *SY = new punct[nr+1];
    punct *DY = new punct[nr+1];
    for( i = 0; i <= nr; i++)
        if( y[i].x < X[mij].x )
        {
            SY[p].x = y[i].x;
            SY[p].y = y[i].y;
            ++p;
        }
        else
        {
            DY[q].x = y[i].x;
            DY[q].y = y[i].y;
            ++q;
        }
    long long d1 = divide ( st, mij, SY, p-1 ) ;
    long long d2 = divide ( mij+1, dr,DY, q-1 ) ;
    long long d = min( d1, d2);         /// d va fi minimul dintre distanta minima a punctelor din stanga verticalei si distanta minima a punctelor din dreapta ei
    long long d_sqrt = ceil(sqrt(d));
    int j,k=0;
    for( i = 0; i <= nr; i++)          /// consideram toate punctele din subproblema actuala
        if( abs( y[i].x - X[mij].x ) <= d_sqrt )          /// daca punctul X[i] se afla la distanta <= d_sqrt fata de verticala,atunci poate contribui la
        {                                                /// distanta minima a 2 puncte din plan; il adaugam in vectorul
            LY[k].x = y[i].x;
            LY[k].y = y[i].y;
            k++;
        }
    for(i = 0; i < k ; i++)             /// pentru fiecare punct i consideram alte 7 puncte cu care ar putea avea distanta minima
        for(j = i + 1 ; j <= (i+7) && j < k; j++)
            d = min(d,dist(LY[i],LY[j]));     /// daca distanta dintre LY[i] si LY[j] < distanta minima gasita pana acum,atunci reactualizam distanta minima

    delete [] SY;
    delete [] DY;
    return d;
}

int main()
{
    f >> n;
    X = new punct[n+1];
    Y = new punct[n+1];
    LY = new punct[n+1];
    for ( int i = 0; i < n ; i++)
    {
        f >> X[i].x >> X[i].y;
        Y[i].x = X[i].x;
        Y[i].y = X[i].y;
    }
    sort(X,X+n,cmpX);           /// dupa absicsa
    sort(Y,Y+n,cmpY);           /// dupa ordonata
    g << fixed << setprecision(6) << sqrt(divide(0,n-1,Y,n-1));
    delete [] X;
    delete [] Y;
    delete [] LY;
    f.close();
    g.close();
    return 0;
}