Cod sursa(job #2974622)

Utilizator RobertlelRobert Robertlel Data 4 februarie 2023 11:55:41
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.83 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <climits>
using namespace std;

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

struct point {
int x , y;
};

vector < point > p;

int n;

bool cmp (point a , point b)
{
    if (a.x < b.x)
        return true;
    if (a.x == b.x && a.y < b.y)
        return true;
    return false;
}

bool cmpaux (point a , point b)
{
    if (a.y < b.y)
        return true;
    if (a.y == b.y && a.x < b.x)
        return true;
    return false;
}

double dist (point a , point b)
{
    long long d1 = a.x - b.x;
    long long d2 = a.y - b.y;
    return sqrt (d1 * d1 + d2 * d2);
}

double distmin (vector < point > &p , int st , int dr)
{
    if (dr - st <= 2)
    {
        double dmin = INT_MAX;

        for (int  i = st ; i < dr ; i++)
        {
            for (int j = i + 1 ; j <= dr ; j++)
                dmin = min (dmin , dist (p[i] , p[j]));
        }
        return dmin;
    }

    int mij = (st + dr) / 2;
    double  dmin = min (distmin (p , st , mij) , distmin (p , mij + 1 , dr));
    double d = (p[mij].x + p[mij + 1].x)/ 2.0;

    vector < point > aux;

    for (int i = st ; i <= dr ; i++)
        if (abs (d - p[i].x) <= dmin)
        aux.push_back (p[i]);

    sort (aux.begin () , aux.end () , cmpaux);
    int n = aux.size ();
    for (int i = 0 ; i < n - 1 ; i++)
    {
        for (int j = i + 1 ; j < i + 8 && j < n ; j++)
            dmin = min (dmin , dist (aux[i] , aux[j]));
    }
    return dmin;
}

int main()
{
    f >> n;
    p.resize (n);
    for (int i = 0 ; i < n ; i++)
    {
        f >> p[i].x >> p[i].y;
    }

    sort (p.begin() , p.end() , cmp);

    g << fixed << setprecision (6) << distmin (p , 0 , n - 1);
    return 0;
}