Cod sursa(job #664194)

Utilizator repp4raduRadu-Andrei Szasz repp4radu Data 19 ianuarie 2012 19:52:17
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.93 kb
#include <cstdio>
#include <algorithm>
#include <cmath>

#define MAX 100050

using namespace std;

int n, p[MAX];

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

bool cmpx(punct a, punct b)
{
    return a.x < b.x;
}

bool cmpy(int a, int b)
{
    return v[a].y < v[b].y;
}

double distanc(int i , int j)
{
    double dist;
    dist = (v[i].x - v[j].x) * (v[i].x - v[j].x);
    dist += (v[i].y - v[j].y) * (v[i].y - v[j].y);
    return sqrt(dist);
}

void citire()
{
    freopen("cmap.in", "r", stdin);
    scanf("%d\n", &n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d %d\n", &v[i].x, &v[i].y);
    }
    fclose(stdin);
}

double min(double a, double b)
{
    if(a < b)
        return a;
    return b;
}

double solve(int left, int right)
{
    double minimumDistance;
    if(right - left + 1 <= 3)
    {
        minimumDistance = distanc(left, right);
        if(right - left == 2)
        {
            minimumDistance = min(minimumDistance, distanc(left + 1, right));
            minimumDistance = min(minimumDistance, distanc(left, left + 1));
        }
        return minimumDistance;
    }
    int mij = (left + right) / 2;
    minimumDistance = min(solve(left, mij), solve(mij + 1, right));
    int k = 1;
    for(int i = left; i <= right; i++)
    {
        if(abs(v[i].x - v[mij].x) <= minimumDistance)
        {
            p[k++] = i;
        }
    }
    sort(p + 1, p + k, cmpy);
    for(int i = 2, j = 1; i < k; i++)
    {
        while(v[ p[i]].y - v[ p[j]].y >= minimumDistance)
            j++;
        for(int h = j; h < i; h++)
        {
            minimumDistance = min(minimumDistance, distanc(h, i));
        }
    }
    return minimumDistance;
}

void afisare()
{
    freopen("cmap.out", "w", stdout);
    printf("%.6lf", solve(1, n));
    fclose(stdout);
}

int main()
{
    citire();
    sort(v + 1, v + n + 1, cmpx);
    afisare();
    return 0;
}