Answer to Question #273822 in C for Rahul Sigh

Question

Alice is playing with bubbles. She is standing at the point of (0,0) and has created N bubbles.

 

Each bubble can be characterized by three parameters :

 

V : denoting the size of the bubble

X : denoting the x coordinate of the bubble

Y : denoting the y coordinate of the bubble

 

The following process will take place as long as there are two or more bubbles left :

 

Alice will choose the bubble closest to her (in case there are multiple options for a bubble she will choose the largest one among them). Note: Here the distance between two points (x1, y1) and (x2,y2) is equal to

 

(Whole Root) (x1-x2)^2 + (y1-y2)^2

  

Let the two bubbles chosen have parameters as [v1, x1, y1 ] (first bubble) and [v2,x2,y2] (second bubble) respectively.

 

She will merge the two bubbles chosen and a new bubble with parameters [ v1 + v2, x1-x2, y1-y2] will be formed.

  

Task :

 

Determine the coordinates of the last bubble left after the process ends.

Answer 1

#include <stdio.h>
#include <math.h>
#define N 50


struct Bubble {
    double v, x, y;
};


void swap(struct Bubble* a, struct Bubble* b) {
    double tmp;


    tmp = a->x;
    a->x = b->x;
    b->x = tmp;
    tmp = a->y;
    a->y = b->y;
    b->y = tmp;
    tmp = a->v;
    a->v = b->v;
    b->v = tmp;
}

int distance(x1, y1, x2, y2) {
    return (int) sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
}

void move_min_dist_to_end(struct Bubble bubbles[], int n) {
    int min_dist = distance(bubbles[0].x, bubbles[0].y, 0, 0);
    int dist;
    int i, i_min = 0;
    for (i=1; i<n; i++) {
        dist = distance(bubbles[i].x, bubbles[i].y, 0, 0);
        if ( dist < min_dist) {
            min_dist = dist;
            i_min = i;
        }
        else if (dist == min_dist) {
            if (bubbles[i].v > bubbles[i_min].v) {
                min_dist = dist;
                i_min = i;
            }
        }
    }
    if (i_min != n-1) {
        swap(&bubbles[i_min], &bubbles[n-1]);
    }
}

int main() {
    struct Bubble bubbles[N] = {{1, 2, 3}, {2, 3, 4}, {5, 6, 7}, {2, 3, 5}};
    int n = 4;

    while (n > 1) {
       move_min_dist_to_end(bubbles, n);
       move_min_dist_to_end(bubbles, n-1);
       n--;
       bubbles[n-1].x = bubbles[n].x - bubbles[n-1].x;
       bubbles[n-1].y = bubbles[n].y - bubbles[n-1].y;
       bubbles[n-1].v = bubbles[n].v + bubbles[n-1].v;
    }

    printf("The last bubbles at (%.2lf, %.2lf) has size %.2lf\n", 
           bubbles[0].x, bubbles[0].y, bubbles[0].v);
    
    return 0;
}