How do I find distance between couple of points (x, y) from origin, and then sort the points, who is closest to (0, 0)?

Question

i need to enter number of points(x,y), and then sort the points,from the closest one to (0,0) to the one that is far.. for example:

Enter number of points: 3
Enter point: 1 6
Enter point: 2 5
Enter point: 4 4
Sorted points:(2,5) (4,4) (1,6)

now i did a function that will find the distance,and i did an array and put the distance between two coordinate x and y,and i want to use merge sort to sort the array, my problem is how to go back and print the actual coordinate x y ... (i hope you would understand the problem),what can i do? i thought of putting the cordinate an array and sort them but that won't work :\ (and i didn't learn struct so i can't use unless if there is no other way ...) plz anyone can help me i really have no idea have to continue:\

#include <stdio.h>
#include <stdlib.h>

void Enter_numbers(int x,int *z,int *first_coordinate,int *second_coordinate);
int distance(int a,int b);
void merge(int a[], int na, int b[], int nb, int c[]);
int merge_sort(int ar[], int n);

int main()
{
    int x;
    int *z;
    int *first_coordinate;
    int *second_coordinate;
    printf("Enter number of points: ");
    scanf("%d",&x);
    z=(int*)malloc(x*sizeof(int));
    first_coordinate=(int*)malloc(x*sizeof(int));
    second_coordinate=(int*)malloc(x*sizeof(int));
    Enter_numbers(x,z,first_coordinate,second_coordinate);
    free(z);
    free(first_coordinate);
    free(second_coordinate);
    return 0;
}

int distance(int a,int b)
{
    int dis;
    dis=((a*a)+(b*b));
    return dis;
}

void Enter_numbers(int x,int *z,int *first_coordinate,int *second_coordinate)
{
    int a=0,b=0;
    int i=0;
    int diss=0;
    while(x>0)
    {
        printf("Enter points: ");
        scanf("%d %d",&a,&b);
        diss=distance(a,b);
        z[i]=diss;
        first_coordinate[i]=a;
        second_coordinate[i]=b;
        ++i;
        x--;
    }

}

and the merge sort function i will use after i figure what to do :

int merge_sort(int ar[], int n)
{ 
    int len;
    int *temp_array, *base;

    temp_array = (int*)malloc(sizeof(int)*n);
    if(temp_array == NULL) {
        printf("Dynamic Allocation Error in merge_sort");
        return FAILURE;
    }
    for (len = 1; len < n; len *= 2) {
        for (base = ar; base < ar + n; base += 2 * len) {
            merge(base, len, base + len, len, temp_array);
            memcpy(base, temp_array, 2*len*sizeof(int));
        }
    }
    free(temp_array);
    return SUCCESS;

}

and here is merge ...

void merge(int a[], int na, int b[], int nb, int c[])
{
   int ia, ib, ic;
   for(ia = ib = ic = 0; (ia < na) && (ib < nb); ic++)
   {
       if(a[ia] < b[ib]) {
           c[ic] = a[ia];
           ia++;
       }
       else {
           c[ic] = b[ib];
           ib++;
       }
   }
   for(;ia < na; ia++, ic++) c[ic] = a[ia];
   for(;ib < nb; ib++, ic++) c[ic] = b[ib];

}

Answer 1

I would use a struct for solving this task. If you haven't learned struct yet, this seems to be a good time to learn it. Note: If you really can't use stuct, see the last part of the answer.

With struct it could be something like:

#include <stdio.h>
#include <stdlib.h>

typedef struct
{
    int x;
    int y;
    int squared_distance;
} dpoint;

int squared_dst(int x, int y)
{
    return (x*x + y*y);
}

// Compare function used for sorting    
int compare_dpoint_dst(const void * e1, const void * e2) 
{
    dpoint* p1 = (dpoint*)e1;
    dpoint* p2 = (dpoint*)e2;
    if (p1->squared_distance > p2->squared_distance) return  1;
    if (p1->squared_distance < p2->squared_distance) return -1;
    return 0;
}

void print_dpoint(dpoint dp)
{
    printf("(%d, %d) : sd = %d\n", dp.x, dp.y, dp.squared_distance);
}

#define N 5

int main(void) {
    // Array of points (fixed size for simplicity)
    dpoint ps[N];

    // Dummy input (for simplicity)
    int x[N] = {1,5,2,3,4};
    int y[N] = {9,3,7,1,3};     
    for (int i = 0; i < N; ++i)
    {
        ps[i].x = x[i];
        ps[i].y = y[i];
    }

    // Calculate squared distance for all points
    for (int i = 0; i < N; ++i)
    {
        ps[i].squared_distance = squared_dst(ps[i].x, ps[i].y);
    }

    printf("unsorted:\n");
    for (int i = 0; i < N; ++i)
    {
        print_dpoint(ps[i]);
    }

    // Sort the points
    qsort (ps, sizeof(ps)/sizeof(*ps), sizeof(*ps), compare_dpoint_dst);

    printf("sorted:\n");
    for (int i = 0; i < N; ++i)
    {
        print_dpoint(ps[i]);
    }

    return 0;
}

Notice that you can do the sorting on the squared distance so that you don't need square root in the program.

The program above will generate:

unsorted:
(1, 9) : sd = 82
(5, 3) : sd = 34
(2, 7) : sd = 53
(3, 1) : sd = 10
(4, 3) : sd = 25
sorted:
(3, 1) : sd = 10
(4, 3) : sd = 25
(5, 3) : sd = 34
(2, 7) : sd = 53
(1, 9) : sd = 82

No use of struct

If you for some reason can't use struct, you can use a shadow array to track the sorting but you'll have to write your own sorting. I don't recommend this approach - learn about structinstead. Anyway, it could be something like:

int x[N];
int y[N];
int sd[N]; // squared distance
int sw[N]; // swap order

// read input and calculate distance
// ...

// Fill sw with 0, 1, 2, ....
for (int i=0; i < N; ++i) sw[i] = i; 

mySort(sd, sw, N);

// Now you can use sw for printing
for (int i=0; i < N; ++i)
{
    // print element sw[i]
    printf("(%d,%d)\n", x[sw[i]], y[sw[i]]);
 }  

}

void mySort(int sd[], int sw[], int N)
{
     // .... code for sorting
     // ....

     // Assume that you need to swap element i and j here
     temp = sd[i];
     sd[i] = sd[j];
     sd[j] = temp;
     // Then do exactly the same for sw
     temp = sw[i];
     sw[i] = sw[j];
     sw[j] = temp;

     // ....
     // ....
}