0

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;
}

Billy Thorton
  • 213
  • 1
  • 4
  • 12

0 Answers0