Cod sursa(job #1546639)

Utilizator sulzandreiandrei sulzandrei Data 8 decembrie 2015 14:41:57
Problema Cele mai apropiate puncte din plan Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 3.45 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
{
    int x,y;
    Point(int x=  0,int y = 0 )
    {
        x = this->x;
        y = this->y;
    }
    bool operator ==(Point e);
    friend istream& operator >>(istream &i,Point & p);
    friend ostream& operator <<(ostream& o,Point p);
};
bool Point::operator ==(Point e)
{
    if( this->x == e.x && this->y == e.y)
        return true;
    return false;
}
ostream& operator <<(ostream& o,Point p)
{
    o<<p.x<<" "<<p.y;
    return o;
}
istream& operator >>(istream &i,Point & p)
{
    i>>p.x>>p.y;
    return i;
}
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];
long double distanceBetweenClosestPairofPoint(int st,int dr,Point Y[], int sizeY)
{
    if(  dr - st + 1 > 3)
    {
        int mij = (st+dr)/2;

        Point Ys[mij+2],Yd[mij+2];
        int sizeYd;
        int sizeYs = sizeYd = 0;
        for(int i = 1 ; i <= sizeY ; i++)
            if ( Y[i].x < X[mij].x)
                Ys[++sizeYs] = Y[i];
            else
            {
                if (Y[i].x == X[mij].x)
                    if (Y[i].y <= X[mij].y)
                        Ys[++sizeYs] = X[i];
                    else
                        Yd[++sizeYd] = X[i];
                else
                    Yd[++sizeYd] = X[i];
            }
        //cout<<"Sizey=="<<sizeY<<" nr elemente: Ys"<<sizeYs<<"  nr elemente Yd"<<sizeYd<<'\n';
        long double mins,mind,minm;

        mins = distanceBetweenClosestPairofPoint(st,mij,Ys,sizeYs);
        mind = distanceBetweenClosestPairofPoint(mij+1,dr,Yd,sizeYd);
        minm = min(mins,mind);
        /*for(int i = 1 ; i< sizeY ; i++)
            if (Y[i] == Y[i+1])
                cout<<Y[i]<<" "<<Y[i+1]<<'\n';*/
        for(int i = 1 ; i < sizeY ; i++)
            for(int j  = 1 ; j <= 7 && i+j <= sizeY ; j++)
                if (! (Y[i] == Y[i+j]))
                    minm = min( distance(Y[i].x, Y[i].y, Y[i+j].x, Y[i+j].y), minm);
        //for(auto p = Y.begin() ; p <= p+min(dr-st+1,7) && p!= Y.end() ; p++)
         //   for(int i =  1 ; i <= min(dr-st+1,7) && p + i !=Y.end() ; i++)
           //     minm = min( distance(p->x,p->y,(p+i)->x , (p+i)->y),minm);
        return minm;
    }
    else
    {
        long double d = distance(X[st].x,X[st].y,X[st+1].x,X[st+1].y);
        //cout<<'\n'<<st<<" "<<dr<<" "<<setprecision(6)<<d<<'\n';
        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;
    Point Y[100003];
    for(int i = 1 ; i <= n  ; i++)
        in>>X[i],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;
         }
    });
    sort(Y + 1, Y + n +1 ,[](Point a, Point b){ return (a.y < b.y);});
    out<<setprecision(6)<<fixed<<distanceBetweenClosestPairofPoint(1,n,Y,n);


    return 0;
}