Cod sursa(job #1273835)

Utilizator batistaUPB-Oprea-Cosmin-Dumitru batista Data 22 noiembrie 2014 23:00:50
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.06 kb
//http://www.infoarena.ro/problema/cmap

#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;

#define x first
#define y second
#define INF 1000000000ll
#defin  NMAX 100005
typedef pair<int,int> punct;

int N;
punct P[NMAX], Y[NMAX], Z[NMAX];

double dist(punct A, punct B)
{
    return sqrt( (double)(A.x-B.x)*(A.x-B.x) + (double)(A.y-B.y)*(A.y-B.y) );
}

double solve(int st,int dr)
{
    //tot if-ul are Theta(1)
    if (dr-st <= 2)
    {
        double dmin=INF;
        int i,j;
        //iau toate perechile de puncte si calculez distanta dintre ele
        //sunt maxim 3 perechi
        for (i=st; i<dr; i++)
            for (j=i+1; j<=dr; j++)
                dmin=min(dmin, dist(P[i], P[j]));
        //sortez punctele dupa y, sunt maxim 3 puncte
        sort(Y+st, Y+dr+1);
        return dmin;
    }

    int m=(st+dr)/2, i, j, len=0;
    double dmin=min(solve(st,m), solve(m+1,dr));//T(n/2) + T(n/2)
    //interclasez punctele sortate dupa y
    merge(Y+st, Y+m+1, Y+m+1, Y+dr+1, Z);//Theta(n)
    /*in Z tin punctele aflate la o distanta mai mica sau egala cu distanta minima
     a semiplanului curent  fata de cel mai
     din dreapta punct al semiplanului*/
    copy(Z, Z+dr-st+1, Y+st); //Theta(n)
    for (i=st; i<=dr; i++)
        if (abs(Y[i].y - P[m].x) <= dmin)
            Z[++len]=Y[i];
    /*iau doar cele mai apropiate 7 puncte si calculez dinstanta minima
     dintre ele*/
    for (i=2; i<=len; i++)
        for (j=i-1; j>=1 && i-j<=7; j--)
            dmin=min(dmin, dist(Z[i], Z[j]));
    return dmin;
}

int main()
{
    //
    ifstream f("cmap.in");
    ofstream g("cmap.out");
    int i;
    f>>N;
    for (i=1; i<=N; ++i)
        f>>P[i].x>>P[i].y;
    //sortez punctele dupa x si la x egal dupa y
    sort(P+1,P+N+1);
    //imi salvez punstele in format (y,x) pentru sortarea ulterioara dupa y
    for (i=1; i<=N; ++i)
        Y[i]=make_pair(P[i].y, P[i].x);
    g<<setprecision(6)<<fixed<<solve(1,N)<<"\n";
    f.close();
    g.close();
    return 0;
}