cpair.c 3.01 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98
/**
 * @file cpair.c
 * @author Ivaylo Ivanov 11777707
 * @date 08.12.2018
 *
 * @brief Main program module.
 *
 * 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.
 *
 **/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

float get_x_mean(float *points[2], int arr_len);

int main () {
    char input[__UINT8_MAX__] = ""; ///< An array to save the input to
    float *points[2]; ///< A pointer to a two-valued array to save the points to
    int point_num = 0; ///< Save the number of points

    while(fgets(input, __INT8_MAX__, stdin) != NULL) { ///< Read line by line
        /// Split the input by whitespace as delimiter
        char *x = strtok(input, " ");
        char *y = strtok(NULL, " ");

        if(x != NULL && y != NULL) {
            /// Convert to float and save to the array
            points[point_num][0] = strtof(x, NULL);
            points[point_num][1] = strtof(y, NULL);
            point_num++; ///< Increase the array length
        } else {
            puts("ERROR: Ill-formed line found");
            exit(EXIT_FAILURE);
        }
    }

    if(feof(stdin) == 0) {
        puts("ERROR: An error interrupted the read");
        exit(EXIT_FAILURE);
    }

    if(point_num == 1)
        exit(EXIT_SUCCESS);

    if(point_num == 2) {
        printf("%f %f\n", points[0][0], points[0][1]);
        printf("%f %f\n", points[1][0], points[1][1]);
        exit(EXIT_SUCCESS);
    }

    float x_mean = get_x_mean(points, point_num);

    exit(EXIT_SUCCESS);
}

/**
 * @brief Function to calculate the mean of the X coordinates from a points array
 * @details Loops through the points array, gets the sum of X coordinates and returns the mean
 * @param points - a pointer to an array with the points
 *        point_num - number of points in the array
 * @return mean of all X coordinates
 *
 **/
float get_x_mean(float *points[2], int point_num) {
    float x_sum = 0;
    for(int i = 0; i< point_num; i++) {
        x_sum += points[i][0];
    }
    return x_sum/point_num;
}