unix/cpair

cpair

A program that searches for the closest pair of points in a set of 2D-points

SYNOPSIS
cpair

EXAMPLE
$ cat 1.txt
4.0 4.0
-1.0 1.0
1.0 -1.0
-4.0 -4.0
$ ./cpair < 1.txt
-1.000000 1.000000
1.000000 -1.000000

The program accepts an array of 2D-points as an input from stdin. The input ends at EOF.

The program does the following:

• No output if the array has one point
• The points if the array has 2 points
• Otherwise, the array is split in 2 parts based on the mean of X and sent to 2 different paralell child processes. The parent watches for the return code of the children and terminates with an error if any of the children exit with anything other than success.

Algorithm description when there are more than 2 points:

• P1 and P2 are the closest pairs for the first and the second part respectively.
• Go through all of the pairs between the points from the first half with the second half and save the shortest one in P3.
• Compare P1, P2 and P3 and return the shortest one to stdout.

Note: The description and the example are from the task I got from TU.