Cod sursa(job #2071711)

Utilizator paulcristian97Vasile Paul-Cristian paulcristian97 Data 20 noiembrie 2017 22:03:01
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.97 kb
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

struct punct
{
    int x,y;
};

double distEuclid(punct a, punct b) {
    double x = a.x - b.x;
    double y = a.y - b.y;
    double dist;

    dist = pow(x, 2) + pow(y, 2);
    dist = sqrt(dist);

    return dist;
}

bool cmp1(punct a,punct b)
{
    return a.x < b.x;
}

bool cmp2(punct a,punct b)
{
    return a.y < b.y;
}

vector<punct> X;
vector<punct> Y;

double DivImp(int st,int dr,vector<punct> Y)
{
    if(dr-st < 4)
    {
        double minim = distEuclid(X[st],X[dr]);
        for(int i=st; i<dr; i++)
            for(int j=i+1; j<=dr; j++)
                if(distEuclid(X[i],X[j]) < minim)
                    minim = distEuclid(X[i],X[j]);
        return minim;
    }
    else
    {
        int mij = (st+dr) / 2;
        vector<punct> SY;
        vector<punct> DY;
        for(int i=0; i<Y.size(); i++)
        {
            if(Y[i].x <= X[mij].x)
                SY.push_back(Y[i]);

            if(Y[i].x > X[mij].x)
                DY.push_back(Y[i]);
        }
        double d1 = DivImp(st,mij,SY);
        double d2 = DivImp(mij+1,dr,DY);
        double d = min(d1,d2);
        vector<punct> LY;
        for(int i=1; i<=Y.size(); i++)
            if(abs(Y[i].x - X[mij].x) <= d)
                LY.push_back(Y[i]);

        double d3 = distEuclid(LY[0],LY[LY.size()-1]);
        for(int i=0; i<LY.size()-1; i++)
            for(int j=i+1; j<LY.size(); j++)
                if(distEuclid(LY[i],LY[j]) < d3)
                    d3 = distEuclid(LY[i],LY[j]);
        d = min(d,d3);
        return d;
    }
}

int main()
{
    int n;
    cin>>n;
    for(int i=0; i<n; i++)
    {
        punct t;
        cin>>t.x>>t.y;
        X.push_back(t); Y.push_back(t);
    }
    sort(X.begin(),X.end(),cmp1);
    sort(Y.begin(),Y.end(),cmp2);
    double dist = DivImp(0,n-1,Y);
    cout<<dist<<endl;
    return 0;
}