Click here to Skip to main content
16,015,594 members
Please Sign up or sign in to vote.
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
Updated 12-Sep-23 11:54am
v2

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.
 
Share this answer
 
v3
Comments
merano99 11-Sep-23 4:37am    
I would like to point out my remark that the compiler here ( pt->a + pt->b + pt->c ) sees the danger of an arithmetic overflow. A typecast to double would be necessary.
Rick York 11-Sep-23 13:24pm    
Yes, good point. In my testing I made the triangle struct use doubles which made the casts unnecessary and I forgot to include that in the post.
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.
 
Share this answer
 
v2

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



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900