Cod sursa(job #2072320)

Utilizator alexandra_pAlexandra Pauna alexandra_p Data 21 noiembrie 2017 18:45:46
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.77 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <math.h>
#include <algorithm>
#include <iomanip>

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

struct punct
{
    int x;
    int y;
};
vector <punct> v;

double dist(punct p1, punct p2)
{
    return ((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}

bool compare (punct A, punct B)
{
    if (A.x == B.x)
        return A.y < B.y;
    return A.x < B.x;
}

double solve (int li, int ls)
{
    if (ls - li == 2)
    {
        double x = min(dist(v[li], v[li + 1]), dist(v[li], v[li + 2]));
        return min(x, dist(v[li + 1], v[li + 2]));
    }
    else
        return dist(v[li], v[li + 1]);
}

double combine(double d_min, int li, int mid, int ls)
{
    vector <punct> aux;

    for (int i = li; i <= ls; i++)
        if (abs(v[mid].x - v[i].x) <= d_min)
            aux.push_back(v[i]);

    sort(aux.begin(), aux.end(), compare);

    for (int i = 0; i < (int)aux.size(); i++)
        for (int j = i + 1; j < (int)aux.size(); j++)
            d_min = min(d_min, dist(aux[i], aux[j]));
    return d_min;
}

double divide (int li, int ls)
{
    if (ls - li <= 2)
        return solve(li, ls);

    int mid = (li + ls)/2;

    double d_min = min(divide(li, mid), divide(mid + 1, ls));
    d_min = combine(d_min, li, mid, ls);

    return d_min;
}

int main()
{
    long n;
    f >> n;
    for (int i = 0; i < n; i++)
    {
        punct a;
        f >> a.x;
        f >> a.y;
        v.push_back(a);
    }

    if (n <= 3)
        cout << solve(0, n-1);
    else
    {
        sort(v.begin(), v.end(), compare);
        g << fixed << setprecision(6) << sqrt(divide(0, n-1));
    }
    f.close();
    g.close();

    return 0;
}