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(n2), 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; }