• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Zadanie Mur OIG

Object Storage Arubacloud
0 głosów
399 wizyt
pytanie zadane 7 czerwca 2022 w C i C++ przez pasjonat_algorytmiki Pasjonat (19,540 p.)
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.
komentarz 7 czerwca 2022 przez Whistleroosh Maniak (56,980 p.)
edycja 7 czerwca 2022 przez Whistleroosh
Kierunek obrotu sprawdza się przeważnie przy użyciu iloczynu wektorowego.
komentarz 7 czerwca 2022 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

O co chodziChodzi 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.

komentarz 7 czerwca 2022 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

@Whistleroosh, 

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

komentarz 7 czerwca 2022 przez Whistleroosh Maniak (56,980 p.)
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ć
komentarz 7 czerwca 2022 przez Whistleroosh Maniak (56,980 p.)
Możesz założyć że współrzędna z = 0 i będziesz miał 3 wymiary :)
komentarz 7 czerwca 2022 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
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ą.
komentarz 7 czerwca 2022 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

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

Jest to nowe zagadnienie dla mnie.

1
komentarz 7 czerwca 2022 przez Whistleroosh Maniak (56,980 p.)

Ż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ą

1
komentarz 7 czerwca 2022 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Ok, widzę, że są napisy po polsku, więc poglądam te jego filmy.

1 odpowiedź

0 głosów
odpowiedź 9 czerwca 2022 przez jankustosz1 Nałogowiec (35,940 p.)
wybrane 17 lutego 2023 przez pasjonat_algorytmiki
 
Najlepsza

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.

1
komentarz 9 czerwca 2022 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

 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!!!

Podobne pytania

0 głosów
0 odpowiedzi 457 wizyt
pytanie zadane 16 maja 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
0 głosów
2 odpowiedzi 401 wizyt
pytanie zadane 28 marca 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
0 głosów
1 odpowiedź 166 wizyt
pytanie zadane 24 marca 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

92,755 zapytań

141,677 odpowiedzi

320,423 komentarzy

62,101 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...