Verifique se um ponto pertence ao polígono convexo em $O(\log N)$

Considere o seguinte problema: você recebe um polígono convexo com vértices inteiros e muitas consultas/queries. Cada consulta é um ponto, para o qual devemos determinar se ele está dentro/no limite do polígono ou não. Suponha que o polígono esteja ordenado no sentido anti-horário. Responderemos a cada consulta em $O(\log n)$ online.

Algoritmo

Vamos escolher o ponto com a menor coordenada x. Se houver vários deles, escolhemos aquele com a menor coordenada y. Vamos denotá-lo como $p_0$. Agora todos os outros pontos $p_1,\dots,p_n$ do polígono são ordenados pelo ângulo polar do ponto escolhido (porque o polígono é ordenado no sentido anti-horário).

Se o ponto pertence ao polígono, ele pertence a algum triângulo $p_0, p_i, p_{i + 1}$ (talvez mais de um, se estiver no limite dos triângulos). Considere o triângulo $p_0, p_i, p_{i + 1}$ de modo que $p$ pertença a esse triângulo e $i$ seja o máximo entre todos esses triângulos.

Há um caso especial, $p$ está no segmento $(p_0, p_n)$. Neste caso, verificaremos separadamente. Caso contrário, todos os pontos $p_j$ com $j \le i$ estão no sentido anti-horário de $p$ em relação a $p_0$, e todos os outros pontos não estão no sentido anti-horário a partir de $p$. Isso significa que podemos aplicar binary search para procurar o ponto $p_i$, de modo que $p_i$ não esteja no sentido anti-horário de $p$ em relação a $p_0$, e $i$ seja o máximo entre todos esses pontos. E depois verificamos se os pontos estão realmente no triângulo determinado.

O sinal de $(a - c) \times (b - c)$ nos dirá, se o ponto $a$ está no sentido horário ou anti-horário a partir do ponto $b$ em relação ao ponto $c$. Se $(a - c) \times (b - c) > 0$, então o ponto $a$ está à direita do vetor que vai de $c$ para $b$, o que significa no sentido horário de $b$ em relação a $c$. E se $(a - c) \times (b - c) < 0$, então o ponto está à esquerda ou no sentido anti-horário. E está exatamente na linha entre os pontos $b$ e $c$.

De volta ao algoritmo: Considere uma consulta de ponto $p$. Primeiramente, devemos verificar se o ponto está entre $p_1$ e $p_n$. Caso contrário, já sabemos que ele não pode fazer parte do polígono. Isso pode ser feito verificando se o produto vetorial $(p_1 - p_0)\times(p - p_0)$ é zero ou tem o mesmo sinal com $(p_1 - p_0)\times(p_n - p_0)$, e $(p_n - p_0)\times(p - p_0)$ é zero ou tem o mesmo sinal com $(p_n - p_0)\times(p_1 - p_0)$. Em seguida, tratamos do caso especial em que $p$ faz parte da linha $(p_0, p_1)$. E então podemos executar binary search no último ponto de $p_1,\dots p_n$ que não está no sentido anti-horário de $p$ em relação a $p_0$. Para um único ponto $p_i$ essa condição pode ser verificada - verificando se $(p_i - p_0)\times(p - p_0) \le 0$. Depois de encontrarmos esse ponto $p_i$, precisamos testar se $p$ existe dentro do triângulo $p_0, p_i, p_{i + 1}$. Para testar se ele pertence ao triângulo, podemos simplesmente verificar se $|(p_i - p_0)\times(p_{i + 1} - p_0)| = |(p_0 - p)\times(p_i - p)| + |(p_i - p)\times(p_{i + 1} - p)| + |(p_{i + 1} - p)\times(p_0 - p)|$. Isto verifica se a área do triângulo $p_0, p_i, p_{i+1}$ tem exatamente o mesmo tamanho da soma dos lados do triângulo $p_0, p_i, p$, do triângulo $p_0, p, p_{i+1}$ e do triângulo $p_i, p_{i+1}, p$. Se $p$ estiver fora, a soma desses três triângulos será maior que o tamanho do triângulo. Se estiver dentro, será igual.

Implementação

A função prepair garantirá que o menor ponto lexicográfico (menor valor $x$ e menor valor $y$) seja $p_0$, e calculará os vetores $p_i - p_0$. Posteriormente, a função pointInConvexPolygon calcula o resultado de uma consulta.

struct pt{
    long long x, y;
    pt(){}
    pt(long long _x, long long _y):x(_x), y(_y){}
    pt operator+(const pt & p) const { return pt(x + p.x, y + p.y); }
    pt operator-(const pt & p) const { return pt(x - p.x, y - p.y); }
    long long cross(const pt & p) const { return x * p.y - y * p.x; }
    long long dot(const pt & p) const { return x * p.x + y * p.y; }
    long long cross(const pt & a, const pt & b) const { return (a - *this).cross(b - *this); }
    long long dot(const pt & a, const pt & b) const { return (a - *this).dot(b - *this); }
    long long sqrLen() const { return this->dot(*this); }
};

bool lexComp(const pt & l, const pt & r){
    return l.x < r.x || (l.x == r.x && l.y < r.y);
}

int sgn(long long val){
    return val > 0 ? 1 : (val == 0 ? 0 : -1);
}

vector<pt> seq;
int n;

bool pointInTriangle(pt a, pt b, pt c, pt point){
    long long s1 = abs(a.cross(b, c));
    long long s2 = abs(point.cross(a, b)) + abs(point.cross(b, c)) + abs(point.cross(c, a));
    return s1 == s2;
}

void prepare(vector<pt> & points){
    n = points.size();
    int pos = 0;
    for(int i = 1; i < n; i++){
        if(lexComp(points[i], points[pos]))
            pos = i;
    }
    rotate(points.begin(), points.begin() + pos, points.end());

    n--;
    seq.resize(n);
    for(int i = 0; i < n; i++)
        seq[i] = points[i + 1] - points[0];
}

bool pointInConvexPolygon(pt point){
    if(seq[0].cross(point) != 0 && sgn(seq[0].cross(point)) != sgn(seq[0].cross(seq[n - 1])))
        return false;
    if(seq[n - 1].cross(point) != 0 && sgn(seq[n - 1].cross(point)) != sgn(seq[n - 1].cross(seq[0])))
        return false;

    if(seq[0].cross(point) == 0)
        return seq[0].sqrLen() >= point.sqrLen();

    int l = 0, r = n - 1;
    while(r - l > 1){
        int mid = (l + r)/2;
        int pos = mid;
        if(seq[pos].cross(point) >= 0)l = mid;
        else r = mid;
    }
    int pos = l;
    return pointInTriangle(seq[pos], seq[pos + 1], pt(0, 0), point);
}

Problemas

SGU253 Theodore Roosevelt