Cod sursa(job #2070748)

Utilizator StefaanStefanescu Stefan Stefaan Data 19 noiembrie 2017 21:18:56
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2 kb
#include <iostream>
#include <fstream>
#include <math.h>
#include <iomanip>
#include <float.h>
#include <algorithm>
using namespace std;

typedef struct
{
    double  x, y;
}punct;

int n;
punct P[100], aux[100], inter[100];

void citire()
{
    ifstream f("cmap.in");
    f >> n;
    for(int i = 0; i < n; i++)
        f >> P[i].x >> P[i].y;
    f.close();
}

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

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

double minim_brut(punct P[], int n)
{
    double min = DBL_MAX;
    for (int i = 0; i < n; i++)
        for (int j = i+1; j < n; j++)
            if (dist(P[i], P[j]) < min)
                min = dist(P[i], P[j]);
    return min;
}

double minDist(int st, int dr)
{
    if(dr-st <= 3)
        return minim_brut(P, dr-st);

    else
    {
        int mid = (st+dr) / 2;
        double centru = P[mid].x;
        double delta = min(minDist(st, mid), minDist(mid+1, dr));
        int r = 0;
        int radDelt = sqrt(delta);

        int i, j, k;
        i = k = st; j = mid+1;
        while(i <= mid && j < dr)
        {
            if(P[i].y < P[j].y)
                aux[k++] = P[i++];
            else
                aux[k++] = P[j++];
        }
        while(i <= mid)
            aux[k++] = P[i++];
        while(j <= dr)
            aux[k++] = P[j++];

        for(i = st; i < dr ; i++)
        {
            P[i] = aux[i];
            if(P[i].x - centru <= radDelt && P[i].x - centru >= -radDelt)
                inter[++r] = P[i];
        }

        for(i = 1; i <= r; i++)
        {
            j = min(r, i+7);
            for(k = i+1; k <= j; k++)
                delta = min(delta, dist(inter[i], inter[k]));

        }
    return delta;
    }
}

int main()
{
    citire();

    sort(P+1 ,P+n+1, comp);

    ofstream g("cmap.out");
    g << setprecision(6) << fixed << sqrt(minDist(0, n));
    g.close();

    return 0;
}