Cod sursa(job #2493770)

Utilizator andreim98Andrei Manolache andreim98 Data 16 noiembrie 2019 20:39:03
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.69 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 || (x.x == y.x && x.y < y.y));
}

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

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

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

    fin.close();
}

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

    return 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 4e18;

    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]);
    }

    else if(st + 2 == dr) // sunt 3 numere
    {
        long long mini = 4e18;

        for(i=st;i<dr;i++)
         for(j=i+1;j<=dr;j++)
          mini = min(mini,distanta(v[i],v[j]));

        interclasare(v,st,st+1,dr);

        return mini;
    }

    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 = 4e18;
    int ssize = aux.size();
    for(i = 0; i < ssize-1; i++)
        for(j = i+1; j < ssize && 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)<<sqrt(DIVIDE_ET_IMPERA(v,0,n-1));

    fout.close();
}