Cod sursa(job #1695200)

Utilizator cristid9Cristi D cristid9 Data 26 aprilie 2016 18:51:59
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.3 kb
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <algorithm>

#define STRIVE_POINTS 8

using namespace std;

struct Point
{
    double x, y;
};

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

int compareY(const void *arg1, const void *arg2)
{
    Point p1 = *((Point *)arg1);
    Point p2 = *((Point *)arg2);

    return p2.y - p1.y;
}

int compareX(const void *arg1, const void *arg2)
{
    Point p1 = *((Point *)arg1);
    Point p2 = *((Point *)arg2);

    return p2.x - p1.x;
}

double __getStriveDist(Point *strive, Point midPoint, size_t size, double delta)
{
    // here we should also sort the points
    qsort(strive, size, sizeof(Point), compareY);

    double minDist = delta;

    for (int i = 0; i < size; ++i)
    {
        for (int j = i + 1; j < size 
                && (strive[j].y - strive[i].y) < minDist; ++j)
        {
            minDist = min(strive[j].y - strive[i].y, minDist);
        }
    }

    return minDist;
}

double __getSmallestDist(Point *points, size_t size)
{
    if (size <= 3)
    {
        double d1 = dist(points[0], points[1]);
        if (size == 2)
        {
            return d1;
        }

        double d2 = dist(points[1], points[2]);
        return min(d1, d2);
    }

    int mid = size / 2;

    Point midPoint = points[mid];
    double dist1 = __getSmallestDist(points, mid);
    double dist2 = __getSmallestDist(points + mid, size - mid);

    double delta = min(dist1, dist2);

    Point strive[STRIVE_POINTS];
    size_t count = 0;
    for (int i = 0; i < size; ++i)
    {
        if (i == mid) continue;

        if (dist(points[i], midPoint) < delta)
        {
            strive[count++] = points[i];
        }
    }

    double dist3 = __getStriveDist(strive, midPoint, count, delta);

    return min(dist3, delta);
}

double getSmallestDist(Point *points, size_t size)
{
    // here we sort the points
    qsort(points, size, sizeof(Point), compareX);

    return __getSmallestDist(points, size);
}

Point points[1005];

int main()
{
    int n;

    scanf("%d", &n);

    for (int i = 0; i < n; i++)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        
        points[i].x = x;
        points[i].y = y;


    }
    
    printf("%.6f\n", getSmallestDist(points, n));

    return 0;
}