Cod sursa(job #2521962)

Utilizator mihaidanielmihai daniel mihaidaniel Data 11 ianuarie 2020 19:09:56
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.8 kb
#include <stdio.h>
#include <algorithm>
#include <math.h>
#define INF 0xffffff
using namespace std;

FILE* in   = fopen ("cmap.in",  "r");
FILE* out  = fopen ("cmap.out", "w");

struct Point {int x, y;} arrx[100], arry[100];

int cmpx(const void* a, const void* b)
{
    Point *p1 = (Point *)a, *p2 = (Point *)b;
    return (p1->x - p2->x);
}

int cmpy(const void* a, const void* b)
{
    Point *p1 = (Point *)a, *p2 = (Point *)b;
    return (p1->y - p2->y);
}

double dst(Point p1, Point p2)
{
    return sqrt((p1.x - p2.x)*(p1.x - p2.x)
               +(p1.y - p2.y)*(p1.y - p2.y));
}

double rec (int st, int dr)
{
    if (dr - st < 1) {return INF;} // max one point => dist inf
    if (dr == st + 1) {return dst(arrx[st], arrx[dr]);} // 2 point => min dst = dst of p1 and p2
    if (dr == st + 2) {return min ( dst(arrx[st], arrx[dr]), min (dst(arrx[st], arrx[st+1]), dst(arrx[dr-1], arrx[dr])));}
    int m = st + (dr - st) / 2, nr = 0;
    double d = min (rec(st, m), rec(m+1, dr)), dd;
    dd = d;

    Point mid[dr];
    for (int i = st; i <= dr; ++i)
    {
        if (dst(arrx[m], arrx[i]) < d)
        {
            mid[nr++] = arrx[i];
        }
    }
    qsort (mid, nr, sizeof(Point), cmpy);

    for (int i = 0; i < nr-1; ++i)
    {
        for (int j = i+1; j < nr && (mid[j].y - mid[i].y) < dd; ++j)
        {
            if (dst (mid[i], mid[j]) < dd)
            {
                dd = dst (mid[i], mid[j]);
            }
        }
    }

    return d;
}

int main(void)
{
    int n;
    fscanf (in, "%d", &n);
    for (int i = 0; i < n; ++i)
    {
        fscanf (in, "%d%d", &arrx[i].x, &arrx[i].y);
    }
    fclose (in);

    qsort (arrx, n, sizeof(Point), cmpx);

    fprintf (out, "%.6f", rec(0, n-1));
    fclose (out);
    return 0;
}