Triángulos en la programación competitiva


La geometría es un tema que muchos de ustedes seguro han visto desde edades tempranas en la escuela, ya sea identificar figuras clásicas (cuadrados, triángulos, cíngulos, etc) o si fuiste un poco más osado y te adentraste a calcular área, perímetro, etc.

Pero claro, este contenido es en resumen muy trivial, y si lo encuentras en un problema, seguro eres capaz de resolverlo. Ahora, ¿Qué pasa cuando la cosa se complica, y el problema no es tan trivial? Pues, a lo largo de este tema, te voy a mostrar algunas propiedades generales sobre los triángulos.

Más adelante, y siguiendo el tema de geometría computacional, veremos otros algoritmos más complejos, donde te mostraré:

  •  Convex Hull (Recubrimiento de puntos).
  •  Sweep Line (Barrido de planos).

Triángulos

El primer paso en el estudio de los triángulos, es determinar cuándo estamos en presencia de ellos. Para esto hay dos reglas básicas, que si no se cumplen, entonces la figura no es un triángulo.

  1. La suma de los ángulos, tiene que ser igual a 180 grados.
  2. La suma de dos lados cualquieras, tiene que ser mayor que la amplitud del tercer lado.

A partir de aquí, vamos a pasar a clasificarlos. Un triángulo puede ser clasificado según sus lados y según sus ángulos. Según los lados pueden ser:

  • Equiláteros: los 3 lados iguales.
  • Isósceles: dos lados iguales y uno diferente.
  • Escalenos: todos los lados diferentes.

Ahora, según los ángulos, estos pueden ser:

  1. Acutángulos: los 3 ángulos interiores son menores que 90 grados.
  2. Rectángulos: uno de sus ángulos es igual a 90 grado.
  3. Obtusángulos: uno de ángulos es mayor que 90 grados.

Si te pregunto, ¿Cómo calcular el área de un triángulo? Seguro me dirás: Base*Altura/2, pero, ¿Es la única forma de calcularla? Pues no, porque el área de un triángulo puede ser calculada de disímiles maneras, a continuación te muestro algunas de ellas.

Teorema de Heron

Por medio de este teorema, es posible calcular el área de un triángulo, si conoces la amplitud de los lados. La fórmula es la siguiente:

AreaT=sqrt(s*(s-a)*(s-b)*(s-c))

Nota: para quienes no estén familiarizados con sqrt, es raíz cuadrada.

Donde s, es la semisuma de los lados (a, b y c) del triángulo, esto quiere decir que s=(a+b+c)/2.

Por el ángulo comprendido

Es posible calcular el área de cualquier triángulo, si conoces 2 de sus lados y la amplitud del ángulo comprendido entre los 2 lados. Esto lo puedes hacer, por medio de la siguiente fórmula:

AreaT=a*b*sin(angulo)/2

Otras propiedades que son explotadas en la programación competitiva, son: ¿Cómo determinar el radio de las circunferencias inscrita y circunscrita en un triángulo?

 

Para el cálculo del radio de la circunferencia circunscrita, puedes usar “el teorema del seno” o “ley de senos”, donde en un triángulo dado, se puede formar la relación (lado)-(ángulo opuesto), que a la vez, nos darían la amplitud de este radio multiplicado por 2. La fórmula quedaría como la siguiente:

2*R=a/sin(A)=b/sin(B)=c/sin(C) (solo tienes que despejar la ecuación para calcular R)

Por otra parte, el radio de la circunferencia inscrita, se puede calcular a partir de la fórmula:

AreaT=r*s (s es la semisuma del triángulo) despejando la fórmula

r=AreaT/s

Otra arista de los triángulos muy importante en la geometría, es el caso especial de los triángulos rectángulos, donde llegamos al conocido teorema de Pitágoras.

Partiendo de un triángulo rectángulo, donde diremos que los lados que comprenden al ángulo de 90 grados son los catetos y al otro lado la hipotenusa, entonces el teorema de Pitágoras dice, que el cuadrado de la hipotenusa va a ser igual a la suma de los cuadrados de los catetos, o lo que es lo mismo:

Hip^2=Cat1^2+Cat2^2

fig4

Con referencia a este tema, te dejo una selección de problemas, que puedes resolver, haciendo uso de las propiedades que te mostré anteriormente.

Esto es todo con relación a triángulos en la geometría computacional, próximamente veremos más sobre geometría en programación competitiva, donde haciendo uso de lo visto en el artículo, se resolverán problemas complejos.