Question

Basic C program

Problem: In this assignment, you have to read a text file (in.txt) that contains a set of point coordinates (x,y). The first line of the file contains the number of points (N) and then each line of the file contains x and y values that are separated by space. The value of x and y are an integer. They can be both negative and positive numbers. You have to sort those points in x-axis major order and then write the output into another file (out.txt) in the same format, i.e., each line contains one coordinate point and the value of x and y are space delimited. After writing the sorted points in the file, your program should display “sorted and output written”. After that, your program should prompt the user for an input coordinate point x and y values and your program should perform a binary search to determine whether the point exists in the given list of points. If it is found it should show “Found and record number”.

Answer 1

Code Image:

Input File Image:

Sample Output:

Run 1:

Run 2:

Output File Image:

Code to Copy:

#include <stdio.h>

#include <stdbool.h>

//Implementation of struct type

//of data structure to store x and y

struct coordinatePoints {

     //Declare x and y coor

     int x, y;

};

//Implementation of isSmallCoordinate function

// to check if the point p is smaller than point q geometry wise.

bool isSmallCoordinate(struct coordinatePoints point1, struct coordinatePoints point2) {

    

     //check whether first coordinate of point1.x is less than point2.x

     if (point1.x<point2.x){

          return true;

     }

     // check if the x coordinate is equal than smaller

      // than the y coordinate is selected or not .

     else if (point1.x == point2.x){

          return point1.y<point2.y;

     }   

     else {

          return false;

     }

}

//Implementation of merge function

void arrayElementsmerge(struct coordinatePoints arrPoint[], int l, int midElement, int r) {

     int numberofElements1 = midElement - l + 1;

     int numberofElements2 = r - midElement;

     //Declare i,j,k as type of integer

     int i, j,k;

     struct coordinatePoints left[numberofElements1], right[numberofElements2];

     // copying both elements the subparts

     for (i = 0; i<numberofElements1; i++) {

          left[i] = arrPoint[l + i];

     }

     //Iterate the loop

     for (k = 0; k<numberofElements2; k++) {

          right[k] = arrPoint[midElement + 1 + k];

     }

     //Initailze the i and j

     i = 0;

     j = 0;

     int count = l;

     //Iterate the loop to sorted merging for both

     //left and right parts

     while (i<numberofElements1 && j<numberofElements2) {

          //call isSmallCoordinate function to

          //check which coordinate is smaller

          if (isSmallCoordinate(left[i], right[j])) {

              arrPoint[count++] = left[i++];

          }

          else {

              arrPoint[count++] = right[j++];

          }

     }

    

     //Iterate the loop fill in the remaining values.

     while (i<numberofElements1) {

          arrPoint[count++] = left[i++];

     }

     //Iterate the loop

     while (j<numberofElements2) {

          arrPoint[count++] = right[j++];

     }

     return;

}

//Implementation of mergeSort function

void mergeSort(struct coordinatePoints a[], int left, int right) {

     int midValue;

     //check left value is greater

     //then right

     if (left >=right)

     {

          return;

     }

     midValue = (left + right) / 2;

     //call recursively mergeSort function for left half of elements

     mergeSort(a, left, midValue);

     //call recursively mergeSort function for right half of elements

     mergeSort(a, midValue + 1, right);

     //call merge method to merge both values

     arrayElementsmerge(a, left, midValue, right);

     return;

}

int main() {

     //Declare n,i,p,q ,l , r as type of integer

     int n, i, p, q, l, r;

     //open the in.txt in read mode

     FILE *openfile= fopen("in.txt", "r");

     fscanf(openfile, "%d", &n);

     //Declare struct type of array that stores

     // the points.

     struct coordinatePoints arr[n];

     for (i = 0; i<n; i++) {

          fscanf(openfile, "%d %d", &p, &q);

          arr[i].x = p;

          arr[i].y = q;

     }

     //call mergeSort function

     mergeSort(arr, 0, n - 1);

                                 

     // Writing the contents into output to a file

     //named as out.txt.

     FILE *outfile = fopen("out.txt", "w");

     //Iterate the loop

     for(i=0;i<n;i++){

               fprintf(outfile,"%d %d\n",arr[i].x,arr[i].y);

   }

     //close the file

     fclose(outfile);

     //Display statement

     printf("Sorted and Output written\n");

     // search process through

     //binary search.

     printf("Search input(x,y): ");

     //Get the input from user

     scanf("%d %d", &p, &q);

     //Declare input as type coordinatePoints

     struct coordinatePoints input;

     input.x = p;

     input.y = q;

     l = 0;

     r = n - 1;

     //Iterate the loop

     while (l<r) {

          //Get the midPosition value

          int midPosition = (l + r) / 2;

          //check is there any small coordinate exists

          if (isSmallCoordinate(arr[midPosition], input)) {

              l = midPosition + 1;

          }

          else

          {

              r = midPosition ;

          }

     }

     //check arr[l] is either equal to input

     //if input lies in the list of points or it is greater than input .

     if (arr[l].x == input.x && arr[l].y == input.y) {

          //Display statement

          printf("Output:Found at record %d\n", l + 1);

     }

     else {

          //Display statement

          printf("Output:Not found\n");

     }

     return 0;

}