Cod sursa(job #664207)

Utilizator repp4raduRadu-Andrei Szasz repp4radu Data 19 ianuarie 2012 20:04:19
Problema Cele mai apropiate puncte din plan Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.96 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define MAX 100050

using namespace std;

int n, p[MAX];

struct punct
{
    long long 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);
    ifstream in("cmap.in");
    in>>n;
    for(int i = 1; i <= n; i++)
    {
        in>>v[i].x>>v[i].y;
    }
    in.close();
}

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()
{
    ofstream out("cmap.out");
    out<<fixed<<setprecision(6)<<solve(1, n);
    out.close();
}

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