Min distance in N vertices

merge_distance.cpp

#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <cmath>
using namespace std;

struct Vertex {
    long long x, y;
    Vertex(long long x, long long y) {
        this->x = x;
        this->y = y;
    }
};

bool cmp(const Vertex &a, const Vertex &b) {
    return a.x < b.x;
}

vector <Vertex> arr;

vector <Vertex> generate() {
    vector <Vertex> arr;
    for (int i = 0; i < 8192; i++) {
        Vertex d(0, 0);
        bool c_flag = true;
        while(c_flag) {
            d = Vertex(rand() % 65536, rand() % 65536);
            c_flag = false;
            for (int j = 0; j < i; j++) {
                if (d.x == arr[j].x && d.y == arr[j].y) {
                    c_flag = true;
                    break;
                }
            }
        }
        arr.push_back(d);
    }
    sort(arr.begin(), arr.end(), cmp);
    return arr;
}

long long vertex_dist(const Vertex &a, const Vertex &b) {
    long long _delta_x = a.x - b.x;
    long long _delta_y = a.y - b.y;
    return _delta_x * _delta_x + _delta_y * _delta_y;
}

long long get_dist_ori(const vector <Vertex> &arr) {
    long long result = -1;
    for (int i = 0; i < arr.size(); i++) {
        for (int j = i + 1; j < arr.size(); j++) {
            long long _dist = vertex_dist(arr[i], arr[j]);
            if (result < 0) result = _dist; else result = min(result, _dist);
        }
    }
    return result;
}

int bin_search(const vector<Vertex> &arr, int start, int end, long long x) {
    int mid = (start + end) / 2;
    if (arr[mid].x == x || start + 1 >= end) return mid;
    else if (arr[mid].x < x) return bin_search(arr, mid, end, x);
    else if (arr[mid].x > x) return bin_search(arr, start, mid, x);
}

// [start, end)
long long get_dist_merge(const vector <Vertex> &arr, int start, int end) {
    if (end - start == 2) {
        return vertex_dist(arr[start], arr[end - 1]);
    } else {
        int mid = (start + end) / 2;
        long long _dist = min(get_dist_merge(arr, start, mid), get_dist_merge(arr, mid, end));
        int _l = bin_search(arr, start, end, arr[mid].x - sqrt(_dist)) - 1;
        int _r = bin_search(arr, start, end, arr[mid].x + sqrt(_dist)) + 1;
        if (_l < 0) _l = 0;
        if (_r >= arr.size()) _r = arr.size() - 1;
        for (int i = _l; i <= _r; i++) {
            for (int j = i + 1; j <= _r; j++) {
                _dist = min(_dist, vertex_dist(arr[i], arr[j]));
            }
        }
        return _dist;
    }
}

int run_test() {
    auto data = generate();
    cout << get_dist_ori(data) << " " << get_dist_merge(data, 0, data.size()) << endl;
    return 0;
}

int main() {
    for (int _ = 0; _ <= 1000; _++) run_test();
    return 0;
}