HELPLIRA - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Bruno Oliveira
Tester: Jingbo Shang
Editorialist: Ajay K. Verma

DIFFICULTY:

CAKEWALK

PREREQUISITES:

High school maths

PROBLEM:

Given a set of triangles, find the indices of the triangle with the smallest and the largest area.

QUICK EXPLANATION:

Iterate through the triangles while maintaining the triangle with minimum and maximum area (in case of ties triangle with larger index wins).

EXPLANATION:

The area of a triangle with vertices (x1, y1), (x2, y2), and (x3, y3) is given by

A = 0.5 * abs((x1 * y2 - x2 * y1) + (x2 * y3 - x3 * y2) + (x3 * y1 - x3 * y1))

Since we are only interested in the relative values of the area, we can drop 0.5, so that area calculation does not require floating point arithmetic. Also the limits on the values of xi, yi’s are small enough so we do not need to worry about overflow.

After calculating areas a single pass can be made through the triangles while maintaining the area and index of the triangles with the smallest and largest area. In case of ties the triangle with larger index wins.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

1 Like
2

“(x3 * y1 - x3 * y1)”. Kindly correct this part in formula.

3

i thought area of triangle was area=heightbase/2, which is a=(maxx-minx)(maxy-miny)/2: bnkjdY - Online C++ Compiler & Debugging Tool - Ideone.com

4

And it is, and I believe such approach was still possible, but, my purpose with this problem was actually to introduce the determimant-area formulation as a geometry useful concept :slight_smile:

1 Like
5

@kuruma but whats prob with my ans bro, i am tired of submitting my ans to the prob

6

well, like I said, on this particular task, using the determinant formulation is a lot easier, but, I’d suggest you look trough some accepted solutions and try to find one which is based on the same approach :slight_smile:

1 Like