Cod sursa(job #2487644)

Utilizator zambi.zambyZambitchi Alexandra zambi.zamby Data 5 noiembrie 2019 16:17:16
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.87 kb
#include <stdlib.h>
#include <iostream>
#include <stdio.h>
#include <cmath>
 
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() {
    int n;
    Point points[100];
    cin >> n;
    float a, b;
    for (int i = 0;i < n;i++) {
        cin >> a >> b;
        points[i].x = a;
        points[i].x = b;
    }
    qsort(points, n, sizeof(Point), compare_x);
    float dist = DEI(points, n);
    cout << dist;
 
    return 0;
}