I was implementing a version of the closest pair problem using the algorithmic technique of divide and conquer. However, when I try and compile my code, in several spots I get the error "Expected constant expression". I am aware that arrays are supposed to have constant values in them, but I'm not quite sure what's wrong in this case. I tried to research solutions and many people suggested using malloc, but it seems to be generally frowned upon. Would someone be able to help me fix this? Below is the code with the errors commented hopefully well enough that you can see them. Thank you so much in advance for your help, I really appreciate it!
#include <iostream>
#include <float.h>
#include <stdlib.h>
#include <math.h>
using namespace std;
//A struct to represent the points on an x,y plane
struct Point{
int x, y;
};
//function to sort x coordinates
int compareX(const void* a, const void* b){
Point *p1 = (Point *)a, *p2 = (Point *)b;
return (p1->x - p2->x);
}
//function to sort y coordinates
int compareY(const void* a, const void* b){
Point *p1 = (Point *)a, *p2 = (Point *)b;
return (p1->y - p2->y);
}
//function to find the distance between any two points
float dist(Point p1, Point p2){
return sqrt( (float)(p1.x - p2.x) * (p1.x - p2.x) +
(float)(p1.y - p2.y) * (p1.y - p2.y)
);
}
//utility function to find the minimum of any two float values
float min(float x, float y){
if(x < y)
return x;
else
return y;
}
//brute force function to find the closest of two points
float bruteforce(Point P[], int n){
float min = FLT_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;
}
//function to find the distance between the closest points of a given size
float closestArray(Point array1[], int size, float d){
float min = d; //initialize the minimum distance as d
//go through the points 1 by 1 and try the next until the difference is smaller than d
for (int i=0; i < size; i++)
for (int j= i + 1; j< size && (array1[i].y - array1[i].y) < min; j++)
if(dist(array1[i],array1[j]) < min)
min = dist(array1[i], array1[j]);
return min;
}
float closestPoint(Point Px[], Point Py[], int n){
if(n <= 3)
return bruteforce(Px, n);
//find the middle point
int mid = n/2;
Point midPoint = Px[mid];
//divide the points along the vertical line
Point Pyleft[mid + 1]; //left of vertical line <--- ERROR
Point Pyright[n-mid-1]; //right of vertical line <--- ERROR
int li = 0; //index of left subarray
int ri = 0; //index of right subarray
for ( int i =0; i<n; i++){
if (Py[i].x <= midPoint.x)
Pyleft[li++] = Py[i];
else
Pyright[ri++] = Py[i];
}
//calculate the smallest ditance dl on the left middle point and dr on the right side
float dl = closestPoint(Px, Pyleft, mid);
float dr = closestPoint(Px + mid, Pyright, n-mid);
//find the smaller of the two distances
float d = min(dl, dr);
//build another array Q that contains points closer than d to the line passing through the middle
Point q[n]; // <--- ERROR
int j = 0;
for (int i = 0; i<n; i++)
if(abs(Py[i].x - midPoint.x) < d)
q[j] = Py[i], j++;
return min(d, closestArray(q, j, d) );
}
//function that finds the smallerst distance
float closest(Point P[], int n){
Point Px[n]; //<--- ERROR
Point Py[n]; //<---ERROR
for(int i=0; i < n; i++)
{
Px[i] = P[i];
Py[i] = P[i];
}
qsort(Px, n, sizeof(Point), compareX);
qsort(Py, n, sizeof(Point), compareY);
//recursive function to find smallest distance
return closestPoint(Px, Py, n);
}
int main()
{
Point P[] = {{2, 3}, {12, 30}, {40, 50}, {5, 1}, {12, 10}, {3, 4}};
int n = sizeof(P) / sizeof(P[0]);
cout << "The smallest distance is " << closest(P, n);
return 0;
}