Cod sursa(job #2074052)

Utilizator EduardLatcanEduard Latcan EduardLatcan Data 24 noiembrie 2017 01:04:44
Problema Cele mai apropiate puncte din plan Scor 85
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
#define MAX  100000
#define INF  2e+9

using namespace std;

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

int n, m;

struct punct
{
    int x, y;
} A[MAX], aux[MAX];

bool cmp(const punct& a, const punct& b)
{
    if (a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}

bool cmpy(const punct& a, const punct& b)
{
    if (a.y == b.y)
        return a.x < b.x;
    return a.y < b.y;
}

double dist(punct a, punct b)
{
    double d1,d2,dist;
    d1 = a.x - b.x;
    d2 = a.y - b.y;
    dist = sqrt(pow(d1, 2)+pow(d2,2));
    return dist;
}

double dmin(int left, int right)
{
    if (left == right)
        return INF;
    if (left + 1 == right)
        return dist(A[left], A[right]);
    int med;
    med = (left + right) / 2;
    double minL, minR, mem;
    minL = dmin (left, med);
    minR = dmin (med, right);
    mem = min (minL, minR);
    m = 0;
    for (int i = left; i < right; i++)
        if ((A[i].x <= A[med].x && A[i].x + mem >= A[med].x) || (A[i].x >= A[med].x && A[i].x - mem <= A[med].x))
            aux[++m] = A[i];
    sort (aux + 1, aux + m, cmpy);
    int last = 1;
    for (int i = 0; i < m; i++)
    {
        while (aux[last].y + mem <= aux[i].y)
            last++;
        for (int j = last; j < i; j++)
            mem = min(mem, dist(aux[j], aux[i]));
    }
    return mem;
}

int main()
{
    int n;
    in>>n;
    for (int i = 0; i < n; i++)
        in>>A[i].x>>A[i].y;
    sort(A, A +n, cmp);
    out<<fixed<<setprecision(6)<<dmin(0, n - 1);
    return 0;
}