Cod sursa(job #1676009)

Utilizator andrew_assassin789Andrei Manea andrew_assassin789 Data 5 aprilie 2016 18:01:52
Problema Cele mai apropiate puncte din plan Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include <fstream>
#include <climits>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iomanip>
#define punct pair<long long,long long>
#define x first
#define y second
using namespace std;
vector <punct> X,Y,z;
punct v[100005];
double modul (double x)
{
    if (x<0) return -x;
    return x;
}
inline double dist(punct A, punct B)
{
    return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
double dei(int st, int dr, vector <punct> & X, vector <punct> & Y)
{
    double dmin=UINT_MAX;
    int i,j;
    if (dr-st+1<=2)
    {
        if (st!=dr)
        {
            if (Y[st]>Y[dr]) swap(Y[st],Y[dr]);
            dmin=dist(Y[st],Y[dr]);
        }
        return dmin;
    }
    else
    {
        int mitte=(st+dr)/2;
        dmin=min(dei(st,mitte,X,Y),dei(mitte,dr,X,Y));
        merge(Y.begin()+st,Y.begin()+mitte,Y.begin()+mitte,Y.begin()+dr,v);//se toarna in v;
        for (i=st;i<dr;i++)
        {
            Y[i]=v[i-st];
            if (modul(X[mitte].x-Y[i].y)<=dmin) z.push_back(Y[i]);
        }
        for (i=0;i<z.size();i++)
            for (j=i+1;j<z.size()&&j<i+8;j++)
                dmin=min(dmin,dist(z[i],z[j]));
        z.clear();
        return dmin;
    }
}
int main()
{
    ifstream f("cmap.in");
    ofstream g("cmap.out");
    int n,i;double dmin;
    f>>n;punct p;
    for (i=1;i<=n;i++)
    {
        f>>p.x>>p.y;
        X.push_back(p);
    }
    sort(X.begin(),X.end());
    for (i=0;i<n;i++)
        Y.push_back(make_pair(X[i].y,X[i].x));
    dmin=dei(0,n-1,X,Y);
    g<<fixed<<setprecision(6);
    g<<dmin<<'\n';
    f.close();
    g.close();
    return 0;
}