Cod sursa(job #2487649)

Utilizator zambi.zambyZambitchi Alexandra zambi.zamby Data 5 noiembrie 2019 16:26:49
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.94 kb
#include <stdlib.h>
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <fstream>
using namespace std;
 
struct Point 
{
    float x, y;
};

int compare_x(const void* a, const void* b) 
{
    Point* p = (Point*)a;
    Point* q = (Point*)b;
    if (p->x < q->x)
        return -1;
    return 1;
}
 
int compare_y(const void* a, const void* b) 
{
    Point* p = (Point*)a;
    Point* q = (Point*)b;
    if (p->y < q->y)
        return -1;
    return 1;
}

float distance(Point a, Point b) 
{
    float dist = sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
    return dist;
}
 
float DEI(Point sort_x[100], int n) 
{
    if (n <= 3) 
    {
        float d_min = 500;
        for (int i=0;i<n;i++) 
        {
            for (int j=i+1;j<n;j++) 
            {
                if (distance(sort_x[i], sort_x[j]) < d_min)
                    d_min = distance(sort_x[i], sort_x[j]);
            }
        }
        return d_min;
    }
    int median;
    median = n / 2;
    Point mid_p = sort_x[median];
    float dist_left = DEI(sort_x, median);
    float dist_right = DEI(sort_x + median, n-median);
    float d;
    if (dist_left < dist_right)
        d = dist_left;
    else d = dist_right;
    Point interval[100];
    int cnt = 0;
    for (int i = 0;i < n;i++)
        if (abs(sort_x[i].x - mid_p.x) < d)
            interval[cnt++] = sort_x[i];
    qsort(interval, cnt, sizeof(Point), compare_y);
    for (int i = 0;i < cnt;i++)
        for (int j = i + 1;j < cnt && j < i + 8;j++)
            if (distance(interval[i], interval[j]) < d)
                d = distance(interval[i], interval[j]);
    return d;
}

int main() 
{
    ifstream f("date4.in");
    ofstream g("cmap.out");
    int n;
    Point points[100];
    f>>n;
    float a, b;
    for (int i=0;i<n;i++) 
    {
        f>>a>>b;
        points[i].x = a;
        points[i].y = b;
    }
    qsort(points, n, sizeof(Point), compare_x);
    float dist = DEI(points, n);
    g << dist;
    return 0;
}