Cod sursa(job #1547209)

Utilizator sulzandreiandrei sulzandrei Data 9 decembrie 2015 09:09:13
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 4.58 kb
#include <cmath>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream in("cmap.in");
ofstream out("cmap.out");
const int MAX_NUMBER_OF_POINTS = 100000;                //Numarul maxim de puncte
                                                        // -1000000000 <= absica , ordonata <= 1000000000
const long long  MIN_POINT_VALUE = -1000000000;
const long long  MAX_POINT_VALUE =  1000000000;
struct Point
{
    long long  x,y;                                     //Tipul de date al absicei si al ordonatei
    Point (long long   x = 0, long long y = 0)
    {
        this -> x = x;
        this -> y = y;
    }
}   bleft(MIN_POINT_VALUE,MIN_POINT_VALUE),             //Punctul din cel mai din stanga colt si cel mai de jos     | posibil
    tright(MAX_POINT_VALUE,MAX_POINT_VALUE);            //Punctul din cel mai din dreapt acolt si cel mai de sus    | posibil
long double distance(Point A,Point B)
{
    return sqrt( (B.x - A.x)*(B.x - A.x) + (B.y - A.y)*(B.y - A.y));       //distanta euclidiana intre punctele A(xa,ya) si B(xb,yb)
}
const long long MAX_POINT_DISTANCE = distance(bleft, tright);              //distanta maxima  posibila intre 2 puncte


Point X[MAX_NUMBER_OF_POINTS+1],                        //In X vom tine punctele sortate dupa x apoi dupa y in caz e egalitate cu x
      Y[MAX_NUMBER_OF_POINTS+1];                        //In Y vom sorta pe parcurs punctele dupa y ca la mergesort

long double dBCPP(int st,int dr)                        //Distanta intre cele mai apropiate puncte din plan
{
    if(  dr - st + 1 > 3)                               //Daca |P| > 3 atunci
    {
        int mij = (st+dr)/2;                            //Impartim pe P in 2 jumatati egale
        long double mins,mind,minm;                     //

        mins = dBCPP( st , mij );                       //luam minimul din partea stanga
        mind = dBCPP( mij + 1, dr );                    //si din partea dreapta

        minm = min( mins , mind );                      //si luam nimimul acestor 2 minime

        int mergeSize = dr - st + 1;                    //ne trebuie valoarea lui |P| pentru a stii dimensiunea sirului unde v om avea sortate punctele

        Point Merged[ mergeSize + 2 ];                  //dupa Y
        /*
        Deoarece am iesit dintr-o recursivitate unde am sortat crescator dupa y inainte pozitiile  st...mij din Vectorul Y si pozitiile mij+1..dr
        tot ce trebuie sa facem pentru a avea Y sortat complet trebuie sa interclasam sirurile sortate Y[st..mij] si Y[mij+1,dr]
        si o facem folosind procedura merge
        pointer catre prima valoare ce trb luata in calcult pt primu interval si pointer catre ultima valoare+1 din acel prim interval
        apoi la fel pt al doilea interval si Merged+1 vectoru unde tinem valorile sortate crescator
        */
        merge(Y + st , Y + mij + 1, Y + mij + 1, Y + dr + 1, Merged + 1 , []( Point a, Point b ){ return ( a.y < b.y );} );
        //copiem valorile din Merged inapoi in Y
        copy(Merged+1,Merged+mergeSize+1,Y+st);
        //Ficare punct
        for(int i = st ; i <= dr ; i++)//Pentru fiecare punct din Y
            for(int j  = 1 ; j <= 7 && i+j <= dr && Y[i+j].y - Y[i].y <= minm ; j++)//luam urmatoarele 7 cat timp diferenta dintre cel din Y cele urmatoare este <= minm
                        minm = min(distance(Y[i] , Y[ i+j]), minm);
        return minm;
    }
    else
    {
        for( int i = st ; i<= dr ; i++)
            Y[i] = X[i];
        sort(Y+st,Y+dr+1,[](Point a,Point b){return a.y<b.y;});// Sortam punctele Y[st..dr]
        long double d = MAX_POINT_DISTANCE;                    // tinem in d distanta maxima posibila
        for(int i = st ; i< dr ; i++)
            for(int j = i+1 ; j <= dr; j++)
                d = min( distance(X[i], X[j]) , d);            //aflam in d distanta minima posibila pentru punctele din X[st...dr]
        return d;
    }

}
int main()
{
    int n;
    in>>n;
    for(int i = 1 ; i <= n  ; i++)
        in >> X[i].x >> X[i].y;
    sort(X+1,X+n+1,[](Point a,Point b)                      //Sortam punctele din X dupa abscisa apoi dupa ordonata
    {
         if (a.x < b.x)
            return true;
         else
         {
             if (a.x ==b.x)
                if (a.y <= b.y)
                    return true;
                else
                    return false;
             return false;
         }
    });
    out<<setprecision(6)<<fixed<<dBCPP(1,n);                //afisam distanta intre cele mai apropiate 2 puncte din plan cu 6 zecimale dupa 0
    return 0;
}