Efstathios Chatzikyriakidis

This program demonstrates the use of an array and is representative of the usual situation in which we store data in one array to process them later. It counts the number of pairs of N randomly generated points of the unit square, which can be connected to a line segment of length less than ‘d’, using the point data type. Because the execution time of this program is O(n²), it can’t be used for large N.

You should know that the implementation of the algorithm does not take into account issues of data input validation or proper management of dynamic memory (e.g. avoiding memory leaks) because it is only necessary to highlight the logic of the algorithm.

Interface (point.h) of the data structure ‘point’.

#ifndef _POINT_H
#define _POINT_H

struct point {
  float x, y;
};

float dist (point, point);

#endif // _POINT_H

Implementation (point.cpp) of the data structure ‘point’.

#include <cmath>
#include "point.h"

float
dist (point a, point b) {
 float dx = a.x - b.x;
 float dy = a.y - b.y;

 return sqrt (dx * dx + dy * dy);
}

Driver (main.cpp) – use of the data structure.

#include <iostream>
#include <cstdlib>
#include "point.h"
using namespace std;

float
randFloat () {
  return 1.0 * rand () / RAND_MAX;
}

int
main (int argc, char *argv[]) {
  float d; int N, i, cnt = 0;

  if (!argv[1] || !argv[2])
    return EXIT_FAILURE;

  d = atof (argv[2]);
  N = atoi (argv[1]);

  srand (time (NULL));

  point *a = new point[N];

  for (i = 0; i < N; i++) {
    a[i].x = randFloat ();
    a[i].y = randFloat ();
  }

  for (i = 0; i < N; i++)
    for (int j = i + 1; j < N; j++)
      if (dist (a[i], a[j]) < d)
        cnt++;

  cout << cnt << " pairs within " << d << endl;

  return EXIT_SUCCESS;
}