https://www.codechef.com/MACE2021/problems/MCODE04

PROBLEM LINK: CodeChef: Practical coding for everyone

Author: Setter’s name

Tester: Tester’s name

Editorialist: Editorialist’s name

DIFFICULTY : INTERMEDIATE

PREREQUISITES:

Nill

PROBLEM:

An instructor provided a student with the sides of different triangles and told him to sort the triangle from the smallest area to the largest.

The output should be recorded in the same order of sides as provided in the input section. It is necessary that the inputs should have different areas.

Use Heron’s formula:

S=p(p−a)(p−b)(p−c)

where p=(a+b+c)/2

#QUICK EXPLANATION:

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

#EXPLANATION:

Observation #1: The number of triangles is very small, so there is no need to use an overcomplicated qsort function - you can write a simple bubble or insertion sort and it will work.

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

p1(p1−a1)(p1−b1)(p1−c1)<p2(p2−a2)(p2−b2)(p2−c2) p1(p1−a1)(p1−b1)(p1−c1)< p2(p2−a2)(p2−b2)(p2−c2)

Let’s remember that p=(a+b+c)/2 . Now, if we substitute, we obtain

p(p−a)(p−b)(p−c)=((a+b+c)(a+b-c)(a-b+c)(-a+b+c))/16

And

((a1+b1+c1)(a1+b1-c1)(a1-b1+c1)(-a1+b1+c1))/16 <((a2+b2+c2)(a2+b2-c2)(a2-b2+c2)(-a2+b2+c2))/16 (a1+b1+c1)(a1+b1-c1)(a1-b1+c1)(-a1+b1+c1) <(a2+b2+c2)(a2+b2-c2)(a2-b2+c2)(-a2+b2+c2)

That means, instead of comparing volumes, we can compare (a+b+c)(a+b-c)(a-b+c)(-a+b+c) each triangle without dealing with non-integer values at all.

SOLUTIONS:

Setter's Solution

#include <stdio.h>

#include <stdlib.h>

struct Triangle

{

int a, b, c;

};

int square(struct Triangle t)

{

int a = t.a, b = t.b, c = t.c;

return (a + b + c)(a + b - c)(a - b + c)*(-a + b + c);

}

void sort_by_square(struct Triangle* a, int n)

{

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

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

if (square(a[i]) > square(a[j]))

{

struct Triangle temp = a[i];

a[i] = a[j];

a[j] = temp;

}

}

int main()

{

int n;

scanf(“%d”, &n);

struct Triangle *a = calloc(n, sizeof(struct Triangle));

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

scanf(“%d%d%d”, &a[i].a, &a[i].b, &a[i].c);

sort_by_square(a, n);

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

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

return 0;

}

Tester's Solution

Same Person

Editorialist's Solution

Same Person