Encontrar el área de un polígono simple en $O(N)$

Sea dado un polígono simple (es decir, sin autointersecciones, no necesariamente convexo). Se requiere calcular su área dadas sus vértices.

Método 1

Esto es fácil de hacer si recorremos todas las aristas y sumamos las áreas de los trapecios acotados por cada arista y el eje x. El área debe tomarse con signo para que el área extra se cancele. Por tanto, la fórmula es la siguiente:

$$A = \sum_{(p,q)\in \text{edges}} \frac{(p_x - q_x) \cdot (p_y + q_y)}{2}$$

Código:

double area(const vector<point>& fig) {
    double res = 0;
    for (unsigned i = 0; i < fig.size(); i++) {
        point p = i ? fig[i - 1] : fig.back();
        point q = fig[i];
        res += (p.x - q.x) * (p.y + q.y);
    }
    return fabs(res) / 2;
}

Método 2

Podemos elegir un punto $O$ de forma arbitraria, iterar sobre todas las aristas sumando el área orientada del triángulo formado por la arista y el punto $O$. De nuevo, debido al signo del área, el área extra se cancelará.

Este método es mejor porque se puede generalizar a casos más complejos (como cuando algunos lados son arcos en lugar de rectas)