Quadriláteros

Quadriláteros são figuras geométricas bidimensionais compostas por quatro vértices, quatro arestas e quatro ângulos internos. As relações entre o lados e os ângulos internos permitem a classificação dos quadriláteros, sendo o retângulo o mais comum dentre eles.

Retângulos

Um retângulo é um quadrilátero com os quatro ângulos internos iguais (cada ângulo tem 90º: a soma dos ângulos internos de um quadrilátero é igual a 360º).

Os pares de lados opostos (paralelos) de um retângulo são denominados base e altura. Deste modo, um retângulo pode ser representado de duas formas: a primeira dleas é através da medida de sua base e sua altura.

class Rectangle {
public:
    double b, h;

    Rectangle(double base, double height) : b(base), h(height) {}
};

A segunda maneira é representar o triângulo através das coordenadas de vértices opostos. Na matemática o mais comum é utilizar o canto inferior esquerdo e o canto superior direito; na computação gráfica, é o contrário: o canto superior esquerdo e o canto inferior direito. Esta representação tem a vantagem porque permite a fácil dedução da base e da altura, e dá flexibilidade na implementação de algoritmos que agem sobre retângulos.

// Definição da classe Point

class Rectangle {
public:
    Point P, Q;
    double b, h;

    Rectangle(const Point& p, const Point& q) : P(p), Q(q)
    {
        b = fabs(P.x - Q.x);
        h = fabs(P.y - Q.y);
    }

    Rectangle(double base, double height)
        : P(0, 0), Q(base, height), b(base), h(height) {}
};

O perímetro de um retângulo é igual ao dobro da soma de suas dimensões (base e altura); ja á área é o produto de suas dimensões.

class Rectangle {
public:
    // Membros e construtores

    double perimeter() const
    {
        return 2 * (b + h);
    }

    double area() const
    {
        return b * h;
    }
};

Um quadrado é um retângulo com lados iguais. Não há necessidade de implementar uma classe à parte para os quadrados, uma vez que todos os resultados válidos para os retângulos permanecem válidos para os quadrados.

A interseção entre dois retângulos pode ser determinada a partir da interseção entre dos intervalos referentes às projeções dos retângulos nos eixos x e y. A interseção pode ser vazia (não há interseção), um segmento de reta ou um retângulo. Os últimos dois cenários podem ser diferenciados através da área do retângulo resultante (área igual a zero significa um segmento de reta).

// Definição da classe Point
using interval = pair<double, double>;

class Rectangle {
public:
    // Membros e construtores

    bool intersection(const Rectangle& r, Rectangle& inter) const
    {
        auto I = interval(min(P.x, Q.x), max(P.x, Q.x));
        auto U = interval(min(r.P.x, r.Q.x), max(r.P.x, r.Q.x));

        auto a = max(I.first, U.first);
        auto b = min(I.second, U.second);

        if (b < a)
            return false;

        I = interval(min(P.y, Q.y), may(P.y, Q.y));
        U = interval(min(r.P.y, r.Q.y), may(r.P.y, r.Q.y));

        auto c = max(I.first, U.first);
        auto d = min(I.second, U.second);

        if (d < c)
            return false;

        inter = Rectangle(Point(a, c), Point(b, d));

        return true;
    }
};

O caso geral, os lados do retângulo não estão alinhados com os eixos x e y, pode ser tratado interpretando o retângulo como um polígono de quatro lados.

Trapézios

Um trapézio é um quadrilátero que possui apenas um par de lados paralelos. Quando os lados não-paralelos são iguais, o trapézio é dito isósceles.

Os lados paralelos são denominados base maior (B) e base menor (b). A distância entre os lados paralelos é denominada altura (h).

class Trapezium {
public:
    double b, B, h;

    Trapezium(double bv, double Bv, double hv) : b(bv), B(Bv), h(hv) {}
};

A área de um trapézio é dada pela metade do produto entre a altura e a soma de suas bases.

class Trapezium {
public:
    // Membros e construtores

    double area() const
    {
        return 0.5 * (b + B) * h;
    }
};

Paralelogramos

Um paralelogramo é um quadrilátero cujos lados opostos são paralelos. Além do retângulo e do quadrado, outro paralelogramo notável é o losango, que é um paralelogramo cujos lados opostos são iguais (mas não necessariamente os ângulos internos).

A área de um paralelogramo é dado pelo produto de sua base pela altura. Em geral, é preciso determinar a altura, considerando um dos lados como base e usando o ângulo formado com um dos lados adjacentes para montar um triângulo, onde a altura seria o cateto oposto ao ângulo.

No caso do losango, a área pode ser determinada diretamente se conhecidas as medidas das duas diagonais (D e d, denominadas diagonal maior e menor, respectivamente). Neste caso, a área é a metade do produto das diagonais, isto é, A = (Dd)/2.

Exercícios

1. UVA
   1. 155 - All Squares
   2. 490 - Overlapping Rectangles
   3. 11207 - The easiest way
   4. 11345 - Rectangles
   5. 11455 - Behold my quadrangle
   6. 11639 - Guard the Land
   7. 11800 - Determine the Shape
   8. 11834 - Elevator
   9. 12256 - Making Quadrilaterals
2. Codeforces
   1. 1A - Theatre Square

Referências

HALIM, Steve; HALIM, Felix. Competitive Programming 3, Lulu, 2013.