Small triangles, large triangles

Question

1.00/5 (1 vote)

See more:

C

#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)
{
    int i,j;
    double p;
    int *S = malloc(n * sizeof(int));
    triangle temp2;
    int temp;

    for(i=0 ; i<n ; i++)
    {
        p = (tr[i].a + tr[i].b + tr[i].c) / 2.0;
        S[i] = sqrt(p * (p-tr[i].a) * (p-tr[i].b) * (p-tr[i].c));
    }

    for(i=0 ; i<n-1 ; i++)
    {
        for(j=0 ; j<n-i-1 ; j++)
        {
            if(S[j] > S[j+1])
            {
                temp2 = tr[j];
                tr[j] = tr[j+1];
                tr[j+1] = temp2;

                temp = S[j];
                S[j] = S[j+1];
                S[j+1] = temp;
            }
        }
    }

    free(S);
}

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;
}

What I have tried:

I have been trying to solve this program on HackerRank, but my code doesn't solve all the test cases. If n is bigger than 10, the program doesn't work correctly. If there is a problem with my code, please let me know.
Note that the program wants to sort a number of triangles based on the area using Heron's formula.
Also, note that "n" is the number of triangles.

Posted 10-Sep-23 9:59am

Ahmed Abdelsalam 2023

Updated 12-Sep-23 11:54am

Deeksha Shenoy

v2

Add a Solution

2 solutions

Solution 1

C

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

p = (tr[i].a + tr[i].b + tr[i].c) / 2.0;
S[i] = sqrt(p * (p - tr[i].a) * (p - tr[i].b) * (p - tr[i].c));

When assigning p, an arithmetic overflow can occur, since initially only int is calculated. Here a conversion into double would be necessary.

With the computation of S[] the decimal places are cut off and thus the result is wrong. With the comparison it can happen then that the order is not correct. It would also be better to check the return value of e.g. malloc.

If you use C++, it would be possible to use std::vector, which would be safer and more convenient
than malloc and free.

You could declare the data type triangle more simply:

C

// struct triangle { int a, b, c; };
// typedef struct triangle triangle;

typedef struct { int a, b, c; }  triangle;

It would also make sense to check if the triangle inequality is satisfied for a, b, c.

Posted 10-Sep-23 12:53pm

merano99

Updated 10-Sep-23 13:33pm

v2

Add a Solution

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Rick York · Accepted Answer · 2023-09-10T14:14:00

If I were you I would write some functions and macros to simplify the code and make it easier to read. Here are some that come to mind :

C

double GetArea( triangle * pt )
{
   double p, area;
   p = ( pt->a + pt->b + pt->c ) / 2.0;
   area = sqrt( p * ( p - pt->a ) * ( p - pt->b ) * ( p - pt->c ) );
   return area;
}

void Print( triangle * tris, double * areas, int count )
{
	int i;
	for( i = 0; i < count; i++)
	{
		printf( "%2d : %5.1f : %2.0f, %2.0f, %2.0f\n",
				i + 1, areas[ i ], tris[ i ].a, tris[ i ].b, tris[ i ].c );
	}
}

Here's a macro for memory allocation :

C

#define ALLOCATE(typ,cnt)  (typ*)calloc(cnt,sizeof(typ))

and here's another one to do the swap :

C

#define SWAP(typ,a,b)    { typ temp; temp = a; a = b; b = temp; }

then your code can look like this :

C

void sort_by_area( triangle* tr, int n )
{
    double * areas = ALLOCATE( double, n );
    int i, j;
    for( i = 0; i < n; i++)
    {
        areas[ i ] = GetArea( & tr[ i ] );
    }

    printf( "before sorting :\n" );
    Print( tr, areas, n );

    for( i = 0; i < n - 1; i++ )
    {
        for( j = i + 1; j < n; j++ )        // note different loop terms
        {
            if( areas[ i ] > areas[ j ] )   // comparison differs also
            {
                SWAP( triangle, tr[ i ], tr[ j ] );
                SWAP( double, areas[ i ], areas[ j ] );
            }
        }
    }

    printf( "after sorting :\n" );
    Print( tr, areas, n );

    free( areas );   // avoid leaking memory
}

Note the different terms in the sorting loops. After the first pass (i=0) the triangle in slot 0 will have the smallest area so you don't need to check it again. Also, there is no need to compare the same one with itself so the inner loop starts one slot after the outer loop. Similarly, the outer loop ends one slot before the last one while the inner loop goes to the last slot.

I added a Print function so I could see all the values.

Small triangles, large triangles

2 solutions

Solution 1

Solution 2

Add your solution here

Preview 0

Small triangles, large triangles

2 solutions

Solution 1

Solution 2

Add your solution here

Preview 0

Existing Members

...or Join us