You are not logged in. Please login at www.codechef.com to post your questions!

×

Editorial - TRIANGCL

PROBLEM LINK:

Practice
Contest

Author: Kanstantsin Sokal
Tester: Pavel Sheftelevich
Editorialist: Pawel Kacprzak

DIFFICULTY:

Cakewalk

PREREQUISITES:

Basic geometry

PROBLEM:


For a given triangle, you have to classify it according to its sides and angles.

QUICK EXPLANATION:


Use Euclidean distance to classify triangles according to their sides. You can use Pythagorean theorem in order to classify them according to their angles.

EXPLANATION:


In this problem, your task is to classify a triangle given as 3 point with integer coordinates. It’s important to notice that there are no degenerated triangles in the input - this ones with all 3 collinear points.

Since all coordinates are integers, we are going to give a solution, which uses only operations over integers in order to avoid any floating point equality checking. This is a common trick, and it’s worth to consider using it while solving this kind of problems.


SUBTASK 1


In the first subtask, you have to classify a triangle based on the lengths of the its sides, and there are two options here: either a triangle has exactly 2 sides of equal lengths or all its sides have different lengths. A triangle with all sides of equal lengths is guaranteed to not appear in the test cases, so we don’t consider such a triangles here.

The task is supposed to be pretty straightforward. Let $d^2(A, B)$ be the squared distance between points $A$ and $B$. In other words, this is the squared length of a side of the triangle between points $A$ and $B$.

Notice that $d^2(A, B)$ can be easily computed $(A.x - B.x)^2$ + $(A.y - B.y)^2$, because its just a squared Euclidean distance.

In order to classify a triangle according to its sides, the only thing we need to do is to compare squared lengths of all its 3 sides. Either none of them are equal or exactly 2 of them are equal, which gives us the answer. Notice that we are using the fact that for two positive integers $C$ and $D$, $C$ and $D$ are equal if and only if $C^2$ and $D^2$ are equal. This let us to avoid floating point operations here.


SUBTASK 2


In the second subtask, besides doing the side classification as in the first subtask, you have to classify triangles according to their angles. More specifically, there are 3 options here. A given triangle may have either one right angle or one obtuse angle or all acute angles.

This seems to be slightly harder than the first subtask. You may think of using some sort of trigonometry functions here, but in fact, there is a quite clever and smooth solution based on Pythagorean theorem.

Let $a^2, b^2, c^2$ be the squared lengths of sides of a triangle in non-descending order. Then the triangle has exactly one right angle if and only if $a^2 + b^2 = c^2$. Moreover, it has exactly one obtuse angle if and only if $a^2 + b^2 < c^2$. Otherwise, all its angles are acute. Since we know how to compute squared lengths of all the sides, we can easily classify a triangle according to its angles using this method. Notice that all these computations are again done only over integers.


AUTHOR'S AND TESTER'S SOLUTIONS:

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

This question is marked "community wiki".

asked 31 Jan '16, 03:50

pkacprzak's gravatar image

5★pkacprzak ♦♦
75485097
accept rate: 12%

edited 31 Jan '16, 22:01

admin's gravatar image

0★admin ♦♦
19.8k350498541


Reading the question and using acos and asin method to compute the angles was a bit harder. Rather simply classifying the triangles based on *Pythagoras theorem* was more clever and an easy task.

link

answered 02 Feb '16, 19:52

pwarriors's gravatar image

5★pwarriors
4815
accept rate: 10%

edited 02 Feb '16, 19:53

I guess applying cosine law or calculating arctans was really an overkill for this problem :P

link

answered 31 Jan '16, 14:04

h1ashdr%40gon's gravatar image

3★h1ashdr@gon
2912320
accept rate: 10%

I couldn't agree more ;)

(31 Jan '16, 14:26) pkacprzak ♦♦5★
1

yea it took me an hour to submit this :p

(31 Jan '16, 20:37) neerajjha_19941★

nice check for finding if triangle is obtuse. Thanks.

link

answered 28 Feb '16, 21:33

esemzv's gravatar image

3★esemzv
212
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×1,688
×968
×647
×167
×42

question asked: 31 Jan '16, 03:50

question was seen: 1,906 times

last updated: 28 Feb '16, 21:33