Encontrar área de um polígono simples em $O(N)$

Seja um polígono simples (isto é, sem auto-interseção, não necessariamente convexo). É necessário calcular sua área, considerando seus vértices.

Método 1

Isso é fácil se percorrermos todas as arestas e adicionarmos áreas trapezoidais delimitadas/ligadas por cada aresta e eixo x. A área precisa ser adiquirida com um sinal para que a área extra seja reduzida. Portanto, a fórmula é a seguinte:

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

Implementação:

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 escolher um ponto $O$ arbitrariamente, iterar sobre todas as arestas, adicionando a área orientada do triângulo formado pela aresta e ponto $O$. Novamente, devido ao sinal de área, a área extra será reduzida.

Esse método é melhor, pois pode ser generalizado para casos mais complexos (como quando alguns lados são arcos em vez de linhas retas).