Cod sursa(job #2488083)

Utilizator zambi.zambyZambitchi Alexandra zambi.zamby Data 6 noiembrie 2019 09:24:19
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.95 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[], Point sort_y[], 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, sort_y,median);
    float dist_right=DEI(sort_x+median, sort_y, n-median);
    float d;
    if (dist_left<dist_right)
        d=dist_left;
    else 
        d=dist_right;
    Point interval[n];
    int cnt=0;
    for(int i=0;i<n;i++)
        if(abs(sort_y[i].x-mid_p.x)<d)
        {    
            interval[cnt] = sort_y[i];
            cnt++;
        }
    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("date4.out");
    int n;
    f>>n;
    Point points[n], v[n];
    for (int i=0;i<n;i++) 
        f>>points[i].x>>points[i].y;
    for(int i=0;i<n;i++)
    {
        v[i].x=points[i].x;
        v[i].y=points[i].y;
    }
    qsort(points, n, sizeof(Point), compare_x);
    qsort(v, n, sizeof(Point), compare_y);
    float dist = DEI(points, v, n);
    g<<dist;
    return 0;
}