Cod sursa(job #1547189)

Utilizator sulzandreiandrei sulzandrei Data 9 decembrie 2015 08:19:31
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.2 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)
{
    if(  dr - st + 1 > 3)
    {
        int mij = (st+dr)/2;
        long double mins,mind,minm;

        mins = dBCPP( st , mij );
        mind = dBCPP( mij + 1, dr );

        minm = min( mins , mind );

        int mergeSize = dr - st + 1;

        Point Merged[ mergeSize + 2 ];

        merge(Y + st , Y + mij + 1, Y + mij + 1, Y + dr + 1, Merged + 1 , []( Point a, Point b ){ return ( a.y < b.y );} );

        copy(Merged+1,Merged+mergeSize+1,Y+st);

        for(int i = st ; i <= dr ; i++)
            for(int j  = 1 ; j <= 7 && i+j <= dr && Y[i+j].y - Y[i].y <= minm ; j++)
                        minm = min( distance(Y[i] , Y[ i+j]), minm);
        return minm;
    }
    else
    {
        sort(Y+st,Y+dr+1,[](Point a,Point b){return a.y<b.y;});
        long double d = MAX_POINT_DISTANCE;
        for(int i = st ; i< dr ; i++)
            for(int j = i+1 ; j <= dr; j++)
                d = min( distance(X[i], X[j]) , d);
        return d;
    }

}
int main()
{
    int n;
    in>>n;
    for(int i = 1 ; i <= n  ; i++)
        in >> X[i].x >> X[i].y,
        Y[i] = X[i];                                        //Citim punctele
    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;
}