Hackerrank Solution- Small Triangles, Large Triangles

Hackerrank Solution- Small Triangles, Large Triangles:

Welcome back Guys!!

In this post we will solve Small Triangles, Large Triangles  Hackerrank problem.

It is a medium level problem using concept of  Structure in C ...

Problem Statement for Small Triangles, Large Triangles hackerrank problem:

You are given  triangles, specifically, their sides ,  and . Print them in the same style but sorted by their areas from the smallest one to the largest one. It is guaranteed that all the areas are different.

The best way to calculate a volume of the triangle with sides ,  and  is Heron's formula:

 where .

Input Format

First line of each test file contains a single integer .  lines follow with ,  and  on each separated by single spaces.

Constraints

• , and 

Output Format

Print exactly  lines. On each line print  integers separated by single spaces, which are ,  and  of the corresponding triangle.

Sample Input 0

3
7 24 25
5 12 13
3 4 5

Sample Output 0

3 4 5
5 12 13
7 24 25

Explanation 0

The square of the first triangle is . The square of the second triangle is . The square of the third triangle is . So the sorted order is the reverse one.

Solution code for  Small Triangles, Large Triangles hackerrank problem:

1) Number of triangles is very small, so there is no need to use overcomplicated qsort function - you can write simple bubble or insertion sort and it will work.

2) We need to calculate volumes of triangles. But we don't need volumes themselves, only their relative comparison. Let's make some transformations:

Let's remember now that . Now, if we substitute, we obtain

and

That means, instead of comparing volumes, we can compare  of each triangle without dealing with non-integer values at all.

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

struct triangle

{

int a;

int b;

int c;

};

typedef struct triangle triangle;

void sort_by_area(triangle *tr, int n) {

// Sort an array a of the length n

    int *p=malloc(n*sizeof(int));

    triangle t; 

//create array of size n to store "volumes"

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

    {

    float a=(tr[i].a+tr[i].b+tr[i].c)/2.0;

//use 2.0 compulsary int/int gives int, int/float gives float

       p[i]=(a*(a-tr[i].a)*(a-tr[i].b)*(a-tr[i].c));

//formula without sqrt as areas are different guarenteed 

//because sqrt dosent work well with float values

    }

//bubble sort

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

    {

        for(int j=0;j<n-i-1;j++)

        {

            if(p[j]>p[j+1])     

            {

                int temp=p[j];

                p[j]=p[j+1];

                p[j+1]=temp;

//swapping array of areas in ascending

//and simuntaneously the structure contents

                t=tr[j];

                tr[j]=tr[j+1];

                tr[j+1]=t;

            }

        }

    }

}

int main()

{

int n;

scanf("%d", &n);

triangle *tr = malloc(n * sizeof(triangle));

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

scanf("%d%d%d", &tr[i].a, &tr[i].b, &tr[i].c);

}

sort_by_area(tr, n);

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

printf("%d %d %d\n", tr[i].a, tr[i].b, tr[i].c);

}

return 0;

}

Please read the code and analysis it properly.

Feel free to share your thoughts  and doubts in the comment section below.

See you next time .