Zadanie Mur OIG

Question

Cześć,

Mam problem z zadaniem Mur z finału 3OIG - https://szkopul.edu.pl/problemset/problem/tafyphqdlVgiX1LUrNYB1ifK/site/?key=statement

Wydaje mi się, że wymyśliłem pomysł działający w O(n) tylko nie wiem jak zaimplementować ten pomysł. A mianowicie:

Porównujemy punkt obserwatora Jacka z 1,2,3,4,5 itd punktem I jest okej jeśli sprawdzimy wszystkie i kierunek obrotu będzie taki sam w sensie(cały czas w lewo albo cały czas w prawo). Problem polega na tym, że nie wiem jak sprawdzić czy kierunek obrotu jest taki sam. Pewnie potrzeba użyć jakieś zawansowanej matematyki, ale nie wiem jak.

Z góry dziękuję za pomoc.

Comments

Kierunek obrotu sprawdza się przeważnie przy użyciu iloczynu wektorowego.

---

Chodzi mi o ten kierunek obrotu

Ps - sory że tak niewyraźnie. I jeśli ten kierunek przesuwa się cały czas w jedną stronę to jest okej.

---

@Whistleroosh, 

Nie znam się jakoś mocno na zawansowanej fizyce, ale iloczyn vectorowy nie tyczy się w 3 wymiarach?

---

A ok. Na początku myślałem że chodzi o kierunek między kolejnymi punktami na obwodzie miasta. Ale ogólnie wygląda jakby mogło działać. Bo inny pomysł jest taki, żeby narysować półprostą między punktem Jacka i jakimś innym punktem i sprawdzić czy ta półprosta przecina więcej niż jeden odcinek. Ale nie wiem czy to się da jakoś szybko zaimplementować

---

Możesz założyć że współrzędna z = 0 i będziesz miał 3 wymiary :)

---

No w sumie racja. Taki pomysł można chyba łatwo zrealizować w O(n^2) sprawdzając wszystkie możliwe opcje przecięć. Jest tam ograniczenie O(n^2) około 70pkt więc to pewnie o to chodzi. Wsumie można się zastanowić czy nie da się tego jakoś przyśpieszyć trzymając np na secie tylko trzeba wymyślić warunek kiedy się najprawdopodobniej przecinają.

---

@Whistleroosh, A znasz jakiś filmik, gdzie dobrze tłumaczą iloczyn vectorowy?

Jest to nowe zagadnienie dla mnie.

---

Żeby zrozumieć iloczyn wektorowy dobrze znać podstawy algebry liniowej. Ja polecam filmiki od 3Blue1Brown i wszystkie jego filmy na ten temat. Tylko to jest po angielsku. Ale ogólnie na OI wystarczy że umiesz policzyć iloczyn wektorowy i znasz jego interpretacje geometryczną

---

Ok, widzę, że są napisy po polsku, więc poglądam te jego filmy.

Answer 1

Whistleroosh Dobrze napisał, że powinieneś użyć iloczynu wektorowego.

Jeżeli masz jakieś dwa odcinki zaczynające się w tym samym punkcie to możesz je zamienić na wektory. Jeżeli a i b będą tymi wektorami to liczysz coś takiego:

a.x*b.y - a.y*b.x jeżeli wynik wyjdzie dodatni to a jest na prawo od b, jeżeli ujemny to a jest na lewo, jeżeli zero to są współliniowe.

Comments

 jankustosz1 Tak wiem, dzieki. Już zrobiłem.

 Whistleroosh baaaaardzo dzięki za polecenie filmików tego gościa. Obejrzałem już pierwsze 10 odcinków i to mi wystarczyło do tego zad.

No tak ogólnie poprostu liczymy iloczyn wektorowy i sprawdzamy czy dodatni czy ujemny i tyle. Kod zadania dającego 100pkt, jak ktoś by kiedyś potrzebował:

#include <iostream>

using namespace std;

struct Element
{
    long long x;
    long long y;
};

long long iloczyn_wektorowy (Element el_1, Element el_2)
{
    long long iloczyn_wektorowy = (el_1.x * el_2.y) - (el_1.y * el_2.x);
    return iloczyn_wektorowy;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int z = 0;
    cin >> z;

    for (int h = 0; h < z; ++h)
    {

        int n = 0;
        bool czy_koniec = false;
        Element jacek;

        cin >> n >> jacek.x >> jacek.y;
        Element elementy[n];

        for (int i = 0; i < n; ++i)
        {
            cin >> elementy[i].x >> elementy[i].y;
            elementy[i].x -= jacek.x;
            elementy[i].y -= jacek.y;
        }

        char kierunek;
        long long iloczyn_wekt = iloczyn_wektorowy(elementy[0],elementy[1]);
        if(iloczyn_wekt == 0)
        {
            cout << "NIE" << endl;
            czy_koniec = true;
        }
        else  if (iloczyn_wekt > 0)
        {
            kierunek = 'P';
        }
        else
        {
            kierunek = 'L';
        }
        for (int i = 1; i < n; ++i)
        {
            // Sztuczka z modulo n.
            long long iloczyn_vect = iloczyn_wektorowy(elementy[i % n],elementy[(i+1) % n]);
            if (iloczyn_vect == 0)
            {
                cout << "NIE" << endl;
                czy_koniec = true;
                break;
            }
            else if (iloczyn_vect > 0)
            {
                if (kierunek == 'L')
                {
                    cout << "NIE" << endl;
                    czy_koniec = true;
                    break;
                }
            }
            else
            {
                if (kierunek == 'P')
                {
                    cout << "NIE" << endl;
                    czy_koniec = true;
                    break;
                }
            }
        }
        if (czy_koniec == false)
        {
            cout << "TAK" << endl;
        }

    }
    return 0;
}

Dzięki wszystkim za pomoc w rozwiązaniu zadania!!!