Cod sursa(job #2493740)

Utilizator andreim98Andrei Manolache andreim98 Data 16 noiembrie 2019 20:07:52
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.37 kb
#include <iostream>
#include<fstream>
#include<vector>
#include<iomanip>
#include <algorithm>
#include <cmath>
using namespace std;

struct punct
{
    long long x,y;
};

int cmp(punct x, punct y)
{
    return x.x<y.x;
}

void citire(vector<punct>&v,int &n)
{
    ifstream fin("cmap.in");

    fin>>n;
    v.resize(n+1);

    for(int i=1;i<=n;i++)
        fin>>v[i].x>>v[i].y;

    fin.close();
}

double distanta(punct x,punct y)
{
    int X = x.x - y.x;
    int Y = x.y - y.y;

    return sqrt(X*X+Y*Y);
}

void interclasare(vector<punct>&v,int st, int mij, int dr)
{
    // interclasam dupa Y

    vector<punct>aux;
    int i = st, j = mij + 1;

    while(i <= mij && j <= dr)
    {
        if(v[i].y < v[j].y)
            aux.push_back(v[j++]);
        else aux.push_back(v[i++]);
    }

    while(i<=mij)
    {
        aux.push_back(v[i++]);
    }

    while(j<=dr)
    {
        aux.push_back(v[j++]);
    }

    for(i = st, j=0; i <= dr; i++,j++)
        v[i] = aux[j];
}

double DIVIDE_ET_IMPERA(vector<punct>&v,int st,int dr)
{
    int i,j,m;
    vector<punct>aux;

    if(st == dr)
        return 2e18;

    if(dr - st == 1) // avem doar 2 puncte
    {
        // sortam dupa y
        if(v[st].y > v[dr].y)
            swap(v[st],v[dr]);

        return distanta(v[st],v[dr]);
    }

    m = (st + dr)/2;

    // distanta minima intre 2 puncte din fiecare cele 2 parti ale "dreptei"
    double dist_min = min(DIVIDE_ET_IMPERA(v,st,m), DIVIDE_ET_IMPERA(v,m+1,dr));

    // sortez dupa y, prin interclasare
    interclasare(v,st,m,dr);

    // tratam cazul in care exista o pereche de puncte situata de o parte si de alta a "dreptei"
    // punem in vectorul aux toate punctele situate la distanta maxima dist_min fata de "verticala"

    for(i = st; i <= dr; i++)
        if(abs(v[i].x - v[m].x) <= dist_min)
            aux.push_back(v[i]);


    double mini = 2e18;

    for(i = 0; i < aux.size()-1; i++)
        for(j = i+1; j < aux.size() && j <= i+8; j++)
         if(distanta(aux[i],aux[j]) < mini)
            mini = distanta(aux[i],aux[j]);

    return min(mini, dist_min);
}

int main()
{
    ofstream fout("cmap.out");

    vector<punct>v;
    int n;
    citire(v,n);
    sort(v.begin(),v.end(),cmp);

    fout<<fixed<<setprecision(6)<<DIVIDE_ET_IMPERA(v,1,n);

    fout.close();
}