Я пытаюсь создать программу, которая будет рассчитывать наименьшее расстояние между парой точек, и я не знаю, как заставить мой код работать. Иногда кажется, что он работает для определенных n входов, но не всегда. Я получаю ошибки повреждения кучи, неверный массив новой длины и самую последнюю Критическую ошибку c0000374 при попытке исправить это. Я предполагаю, что это что-то очень глупое, но я не могу найти решение.
Код основан на: https://www.geeksforgeeks.org/closest-pair-of-points-onlogn-implementation/
#include <iostream>
#include <random>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#define MAX 1;
struct Point {
float x;
float y;
Point()
{
this->x = 0;
this->y = 0;
}
Point(float x, float y) {
this->x = x;
this->y = y;
}
Point *operator=(const Point *other)
{
this->x = other->x;
this->y = other->y;
return this;
}
};
void merge(Point* &arr, int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
Point *L = new Point[n1];
Point *R = new Point[n2];
for (i = 0; i < n1; i++) {
L[i] = &arr[l + i];
}
for (j = 0; j < n2; j++) {
R[j] = &arr[m + 1 + j];
}
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2)
{
if (L[i].x <= R[j].x)
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(Point* &arr, int l, int r)
{
if (l < r)
{
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
int compareX(Point a, Point b) {
return ((float)a.x >= (float)b.x) ? 1 : -1;
};
float dist(Point p1, Point p2)
{
return sqrt((p1.x - p2.x)*(p1.x - p2.x) +
(p1.y - p2.y)*(p1.y - p2.y)
);
}
float stripClosest(Point* &strip, int size, float d)
{
float min = d;
for (int i = 0; i < size; ++i)
for (int j = i + 1; j < size && (strip[j].y - strip[i].y) < min; ++j)
if (dist(strip[i], strip[j]) < min)
min = dist(strip[i], strip[j]);
return min;
}
float min(float x, float y)
{
return (x < y) ? x : y;
}
float bruteForce(Point P[], int n)
{
float min = MAX;
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
if (dist(P[i], P[j]) < min)
min = dist(P[i], P[j]);
return min;
}
float closestUtil(Point P[], Point Pi[], int n)
{
if (n <= 3)
{
return bruteForce(P, n);
}
else
{
int mid = n / 2;
Point midPoint = P[mid];
int li = 0, ri = 0;
Point* Pyl = new Point[mid+1];
Point* Pyr = new Point[n - (mid -1)];
Point* strip = new Point[n];
for (int i = 0; i < n; i++)
{
if (P[i].y <= midPoint.y)
Pyl[li++] = Pi[i];
else
Pyr[ri++] = Pi[i];
}
float dl = closestUtil(P, Pyl, mid);
float dr = closestUtil(P + mid, Pyr, n - mid);
float d = min(dl, dr);
int j = 0;
for (int i = 0; i < n; i++)
if (abs(P[i].y - midPoint.y) < d)
strip[j] = Pi[i], j++;
return min(d, stripClosest(strip, j, d));
}
}
int main() {
int n;
std::cout << "Input the ammount of points" << std::endl;
std::cin >> n;
Point* arr = new Point[n];
std::default_random_engine generator;
std::uniform_real_distribution<float> distribution(0.0, 1.0);
for (int i = 0; i < n; i++)
{
float xi = distribution(generator);
float yi = distribution(generator);
arr[i].x = xi;
arr[i].y = yi;
}
mergeSort(arr, 0, n - 1);
for (int i = 0; i < n; i++)
std::cout << arr[i].x << std::endl;
std::cout << bruteForce(arr, n) << std::endl;
std::cout << closestUtil(arr, arr, n);
return 0;
}