Pripadnost tačke konveksnom mnogouglu

Napiši program koјi utvrđuјe da li tačka pripada konveksnom mnogouglu (ivice mnogougla smatraјu se njegovim delom).

Opis ulaza

Sa standardnog ulaza se učitava broј temena konveksnog mnogougla \(n\) (\(3 \leq n \leq 50000\)), a zatim redom temena u redosledu suprotnom od kazaljke na satu. Svako teme se zadaјe u posebnom redu, pomoću dva cela broјa razdvoјena јednim razmakom. Nakon toga se zadaјe broј \(m\) (\(1 \leq m \leq 50000\)) tačaka čiјu pripadnost mnogouglu treba ispitati, a zatim u narednikh \(m\) redova koordinate tih tačaka (koordinate su celobroјne, razdvoјene јednim razmakom).

Opis izlaza

Za svaku od \(m\) tačaka na standardni izlaz u posebnom redu ispisati da ako tačka pripada mnogouglu tј. ne u suprotnom.

Primer

Ulaz

Izlaz

Rešenje

Opis glavnog rešenja

Svaki konveksni mnogougao se može podeliti na trouglove tako što se povuku sve dijagonale iz njegovog proizvoljnog temena. Tačka pripada mnogouglu ako i samo ako pripada nekom od tih trouglova. Naglasimo da je proveru potrebno malo prilagoditi da bi se u obzir uzelo to da se ivice mnogougla smatraju njegovim delom. Ako jedna tačka leži na datoj duži ona će se smatrati da je sa iste strane te duži kao i bilo koja druga tačka. Takoće, pošto su vrednosti koordinata u ovom zadatku relativno veliki brojevi, potrebno je prilikom izračunavanja vektorskog proizvoda obratiti pažnju na mogućnost nastanka prekoračenja.

Pošto se pripadnost trouglu može ispitati u vremenu \(O(1)\), a posmatramo \(n - 2\) trougla, složenost ispitivanja pripadnosti jedne tačke je \(O(n)\), dok je složenost provere za svih \(m\) tačaka \(O(mn)\).

Zadatak možemo efikasnije rešiti binarnom pretragom. Svaka dijagonala mnogougao deli na dva manja mnogougao. Ako se ustanovi da je tačka sa jedne strane dijagonale, znamo da ona ne može da pripada onom od ta dva mnogougla koji leži sa suprotne strane te dijagonale i potrebno je ispitati samo da li tačka pripada onom drugom mnogouglu. Ako se dijagonala uvek bira tako da ta dva mnogougla imaju približno isti broj temena, problem će se svoditi na problem istog oblika, ali dvostruko manje dimenzije, što daje efikasan algoritam. Polovljenje prekidamo kada ostane trougao i tada vršimo proveru pripadnosti trouglu.

Pošto se u svakom koraku dimenzija problema polovi, složenost pripadnosti jedne tačke je \(O(\log n)\) , dok je složenost provere za svih \(m\) tačaka \(O(m \log n)\).

#include <iostream>
#include <vector>

struct Point {
    double x;
    double y;
};

double orientation(const Point &A, const Point &B, const Point &C) 
{
    return (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);
}

double distance(const Point &A, const Point &B) 
{
    double dx = B.x - A.x;
    double dy = B.y - A.y;

    return dx * dx + dy * dy;
}

bool in_triangle(const Point &A, const Point &B, const Point &C, 
                 const Point &S)
{
    double o1 = orientation(A, B, S);
    double o2 = orientation(B, C, S);
    double o3 = orientation(C, A, S);

    if ((o1 > 0 && o2 > 0 && o3 > 0) ||
        (o1 < 0 && o2 < 0 && o3 < 0)) {
        return true;
    }

    return false;
}

bool in_convex_hull(const std::vector<Point> &CH, const Point &S)
{
    const int n = CH.size();

    if (orientation(CH[0], CH[1], S) < 0 ||  
        orientation(CH[0], CH[n - 1], S) < 0) {
        return false;
    }

    int l = 1;
    int r = n - 1;
    while (r - l > 1) {
        int m = l + (r - l) / 2;
        int o = orientation(CH[0], CH[m], S);
        if (o > 0) {
            r = m;
        } else if (o < 0) {
            l = m;
        } else {
            if (distance(CH[0], S) < distance(CH[0], CH[m])) {
                return true;
            } else {
                return false;
            }
        }
    }

    if (in_triangle(CH[0], CH[l], CH[r], S)) {
        return true;
    }

    return false;
}

int main(int argc, const char *argv[])
{
        
    return 0;
}