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>

using namespace std;

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;
}

// Provera da li se tačka nalazi u trouglu se svodi
// na računanje 3 orijentacije, pri čemu je treća tačka
// uvek S (tačka koju proveravamo), a ostale dve tačke su
// tačke trougla koje rotiramo ciklično. Ukoliko su sve 3
// orijentacije iste, tačka je u trouglu. Pošto se stranice
// mnogougla smatraju njegovim delom, uključujemo i slučaj kada
// je neka orijentacija jednaka 0.
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 vector<Point> &CH, const Point &S)
{
    const int n = CH.size();

    // Provera da li je tačka u prostoru koji ne sadrži mnogougao
    // i određen je tačkama na indeksima 0, 1 i n-1
    if (orientation(CH[0], CH[1], S) < 0 ||
        orientation(CH[0], CH[n - 1], S) > 0) {
        return false;
    }

    // Na početku posmatramo prostor određen tačkama na indeksima 0, 1 i n-1,
    // i sadrži ceo mnogougao koji posmatramo
    int l = 1;
    int r = n - 1;
    // Izvršavamo petlju dok ne suzimo prostor toliko da sadrži samo jedan trougao polaznog mnogougla
    while (r - l > 1) {
        // Prepolovimo trenutni prostor
        int m = l + (r - l) / 2;
        int o = orientation(CH[0], CH[m], S);
        // Na osnovu orijentacije zaključujemo da li se tačka S nalazi u levom ili desnom
        // delu prostora
        if (o > 0) {
            l = m;
        } else if (o < 0) {
            r = m;
        } else {
            // U slučaju da je tačka baš na polupravoj kojom smo prepolovili prostor,
            // proveravamo da li je tačka unutar mnogougla pomoću rastojanja
            if (distance(CH[0], S) <= distance(CH[0], CH[m])) {
                return true;
            } else {
                return false;
            }
        }
    }

    // Na kraju, proveravamo da li je tačka unutar trougla koji pripada
    // mnogouglu ili ne
    if (in_triangle(CH[0], CH[l], CH[r], S)) {
        return true;
    }

    return false;
}

int main()
{
    int n;
    cin >> n;

    vector<Point> CH(n);
    for (int i = 0; i < n; i++) {
        cin >> CH[i].x >> CH[i].y;
    }

    int m;
    cin >> m;

    for (int i = 0; i < m; i++) {
        Point S;
        cin >> S.x >> S.y;

        if (in_convex_hull(CH, S)) {
            cout << "da" << endl;
        } else {
            cout << "ne" << endl;
        }
    }

    return 0;
}