Cod sursa(job #2070883)

Utilizator doodling19Diana Diac doodling19 Data 19 noiembrie 2017 23:42:41
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3.36 kb
#include <iostream>
#include<vector>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<limits>
#include <iomanip>
using namespace std;


ifstream f("cmap.in");
ofstream g("cmap.out");

struct punct
{
    int x,y;
};

bool compara(punct i, punct j)
{
    return (i.x<j.x);
}

bool comparaY(punct i, punct j)
{
    return (i.y<j.y);
}

long double distanta(punct i, punct j)
{
    long double d = sqrt((i.x - j.x)*(i.x - j.x)+(i.y - j.y)*(i.y - j.y));
    return d;
}

long double distMinVector (int stg, int dr, vector<punct> v)//(dr-stg+1)^2 complexitatea
{
    //atinge dreapta!
    long double dmin = distanta(v[stg],v[stg+1]);
    long double d;
    for(int i=stg; i<dr; i++)
    {
        for(int j=i+1; j<=dr; j++)
        {
            d = distanta(v[i],v[j]);
            if(dmin > d)
                dmin = d;
        }
    }
   // cout<<dmin<<endl;
    return dmin;
}

void citire(int &n, vector<punct> &v)
{
    punct z;
    f>>n;
    for(int i=0; i<n; i++)
    {
        f>>z.x>>z.y;
        v.push_back(z);
    }
}


long double divide(int n,int S, int D, vector<punct> X)
{
    punct p1,p2;
    /*if(n<=3)prea mult timp
    {
        return distMinVector(0,n-1,X);
    }*/
     if( D-S == 1)
        return distanta( X[S], X[D] );

    if ( D-S == 2 )
        return min(distanta(X[S], X[S+1]),min(distanta(X[S+1], X[D]),distanta(X[S], X[D])));
    int mij = (S+D)/2;
    //stapaneste
    long double distStg = divide(mij,0,mij-1,X);//nu contine si mijlocul
    long double distDr = divide(n-mij,mij,n-1,X);//contine si mijlocul
    //stop stapaneste
    //Combina/Cucereste
    long double dist = min(distStg,distDr);
    vector<punct> sirY;//contine toate punctele ce sunt la o distanta de cel mult dist de dreapta din mijloc si se sorteaza dupa Y
    int j=0;
    for(int i=S; i<=D; i++) //adaug punctele cu distanta cel mult dist
    {
        if(abs(X[i].x-X[mij].x)<=dist)
        {
            sirY.push_back(X[i]);
            j++;
        }
    }
    //sortez
    sort(sirY.begin(),sirY.end(),comparaY);
    //pt fiecare punct p din sirY cauta in primele 7 puncte care dintre ele sunt la distanta de cel mult dist fata de p
    long double dmin2=dist;//maximul
    for(int i=0; i<(int)sirY.size(); i++)
    {
       long double d1;
        int stop = min((int)sirY.size()-i-1,i+7); //sa vad daca sunt 7 puncte
        //cout<<endl;
        for(int k=i+1; k<=stop; k++)
        {
            //cout<<"1 ";
            //d1 = distanta(X[i],X[k]);
            if((sirY[k].y-sirY[i].y)<=dist)
            {
                d1 = distanta(sirY[i],sirY[k]);
                if(dmin2>d1)
                {
                    dmin2=d1;
                    p1 = sirY[i];
                    p2=sirY[k];
                }
            }

        }
       // cout<<endl;
    }

    return min(dist,dmin2);
}

void lucreaza(int n, vector<punct> &v)
{
    //ordonez v dupa x
    sort(v.begin(),v.end(),compara);
   // cout<<"Vectorul ordonat dupa x: \n";
   /* for(int i=0; i<n; i++)
    {
        cout<<v[i].x<<" "<<v[i].y<<endl;
    }*/
    //cout<<"Distanta minima este: "<< setprecision (9)<<divide(n,0,n-1,v);
    g<< setprecision (9)<<divide(n,0,n-1,v);
}

int main()
{
    int n;//nr de puncte
    vector<punct> v;
    citire(n,v);
    lucreaza(n,v);

    return 0;
}