Cod sursa(job #1546757)

Utilizator sulzandreiandrei sulzandrei Data 8 decembrie 2015 17:56:43
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.56 kb
#include <iostream>
#include <cmath>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream in("cmap.in");
ofstream out("cmap.out");
struct Point
{
    long long  x,y;
    Point(int x=  0,int y = 0 )
    {
        x = this->x;
        y = this->y;
    }
};
long double distance(long long  xa, long long  ya , long long  xb, long long  yb)
{
    long double res = sqrt( (xb - xa)*(xb - xa) + (yb - ya)*(yb - ya));

    return res;
}
Point X[100003],Y[100003];
long double distanceBetweenClosestPairofPoints(int st,int dr)
{
    if(  dr - st + 1 > 3)
    {
        int mij = (st+dr)/2;
        long double mins,mind,minm;

        mins = distanceBetweenClosestPairofPoints(st,mij);
        mind = distanceBetweenClosestPairofPoints(mij+1,dr);
        minm = min(mins,mind);
        int mergeSize = dr-st+1;
        Point Merged[mergeSize+2];
        int i = st;
        int j = mij+1;
        int p = 0;
        while(i <= mij && j <= dr)
            if (Y[i].y <= Y[j].y)
                Merged[ ++ p ] = Y[ i ++ ];
            else
                Merged[ ++ p ] = Y[ j ++ ];
        while(i <= mij )
            Merged[ ++ p ] = Y[ i ++ ];
        while( j <= dr )
            Merged[ ++ p ] = Y[ j ++ ];
        for(int i = st, j = 1 ; i <= dr ; i++,j++)
            Y[i] = Merged[j];
        for(int i = st ; i <= dr ; i++)
            for(int j  = 1 ; j <= 7 && i+j <= dr && Y[i+j].y - Y[i].y <= minm +0.001   ; j++)
                        minm = min( distance(Y[i].x, Y[i].y, Y[i+j].x, Y[i+j].y), minm);
        return minm;
    }
    else
    {
        for(int i = st ; i< dr ; i++)
            for(int j = st+1 ; j <= dr ; j++)
                if (Y[i].y>Y[j].y)
                    swap(Y[i],Y[j]);
        long double d = distance(X[st].x,X[st].y,X[st+1].x,X[st+1].y);
        for(int i = st ; i< dr ; i++)
            for(int j = i+1 ; j <= dr; j++)
                d = min(distance(X[i].x,X[i].y,X[j].x,X[j].y),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];
    sort(X+1,X+n+1,[](Point a,Point b)
    {
         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<<distanceBetweenClosestPairofPoints(1,n);


    return 0;
}