Zadanie Radio, KI Staszic, geomatria analityczna.

Question

Mam problem z takim zadaniem: https://ki.staszic.waw.pl/task.php?name=radio

Napisałem bruta O(N^3) na 60pkt, sprawdzam, że każdy z punktów jest wynikiem i sprawdzam każdą parę czy kąt pomiędzy wektorami idącymi z tego punktu startowego do tych dwóch punktów nie jest > 90 stopni, robiąc to iloczynem skalarnym, x1*x2 + y1*y2. Miałem pomysł, żeby jakoś je posortować i gąsienicę, ale nwm czy to się da. 

Kod dający 60pkt:

#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

struct Punkt
{
    int y;
    int x;
};

int n = 0;
bool czy_pasuje = false;
vector<Punkt> punkty;
vector<int> wyn_vect;

inline void symuluj(int idx1, int idx2)
{
    if ((ll)punkty[idx1].x * (ll)punkty[idx2].x + (ll)punkty[idx1].y * (ll)punkty[idx2].y < 0)
        czy_pasuje = false;
}

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

    cin >> n;
    punkty.assign(n,{});
    for (int i = 0; i < n; ++i)
        cin >> punkty[i].x >> punkty[i].y;

    for (int i = 0; i < n; ++i)
    {
        Punkt start = punkty[i];
        czy_pasuje = true;
        for (int j = 0; j < n; ++j)
        {
            punkty[j].x -= start.x, punkty[j].y -= start.y;
        }
        for (int j = 0; j < n and czy_pasuje == true; ++j)
        {
            if (j == i)
                continue;
            for (int k = 0; k < n and czy_pasuje == true; ++k)
            {
                if (i == k or j == k)
                    continue;
                symuluj(j,k);
            }
        }
        for (int j = 0; j < n; ++j)
        {
            punkty[j].x += start.x, punkty[j].y += start.y;
        }
        if (czy_pasuje == true)
            wyn_vect.push_back(i);
    }


    cout << wyn_vect.size() << '\n';
    for (int i = 0; i < wyn_vect.size(); ++i)
        cout << wyn_vect[i] + 1 << '\n';

    return 0;
}

Z góry dzięki!

Comments

mam jedynie pomysł, że każdy punkt będzie na otocze wypukłej (chyba)

Answer 1

A nie wystarczy zaimplementować otoczki wypukłej i sprawdzić jedynie dla każdego punktu z otoczki dwa sąsiednie?

Comments

Wystarczy. Jeśli zadanie jest geometryczne, to prawdopodonieństwo, że jest to coś na otoczkę jest całkiem duże

---

Pierwszy raz w życiu piszę sortowanie kątowe, i taka funkcja do sorta punktów kątowo względem punktu o współrzędnych y_poczatkowe i x_poczatkowe jest ok? Chodzi mi o operator. y_poczatkowe i x_poczatkowe to współrzędne punktu o najmniejszym y, a w przypadku remisów po y, najmniejszy x.(obliczam je w programie 0,0 tylko inicjalnie), wokół niego chcę posortować kątowo i zastosować algorytm Grahama(tak wyczytałem, że chyba to się robi), bo wiem, że ten punkt napewno będzie na otoczce.

int y_poczatkowy = 0, x_poczatkowy = 0;

struct Punkt
{
    int y;
    int x;
    int idx;
    ld kat() const
    {
        if (x == x_poczatkowy)
            return ld(M_PI) / ld(2);
        return atan2(ld(y - y_poczatkowy), ld(x - x_poczatkowy));
    }
    bool operator < (const Punkt &punkt) const
    {
        return kat() < punkt.kat();
    }
};

 

---

Jak je posortowałem na przykładowym teście, to wygląda jakby dobrze posortował.

---

Bo boję się, jedynie, że ten atan2 to zwraca zmiennoprzecinkowe, i zastanawiam się czy się nie da tego uwalić.

---

Dlatego lepiej korzystać z cross product. Możesz posortować punkty sprawdzając orientacje 2 dowolnych punktów z punktem względem którego sortujesz. Ta metoda chyba nie działa jeśli kąty między punktami będą większe niż 180

---

Dostaję 90pkt, jeden test daje odpowiedź 3 zamiast 4. Zmieniłem sortowanie na iloczyn wectorowy, tylko zastanawiam się czy to już jest dobre, czy ten iloczyn wektorowy się wywali w jakimś szczególnym przypadku?

struct Punkt
{
    ll y;
    ll x;
    ll idx;
    bool operator < (const Punkt &inny) const
    {
        return (y - y_poczatkowy) * (inny.x - x_poczatkowy) < (inny.y - y_poczatkowy) * (x - x_poczatkowy);
    }
};

 

---

Już dobiłem do setki. Bład był, jak sortowałem kątowo(operator) i punkty były na jednej prostej, i iloczyn wektorowy był taki sam, więc brał dowolne punkty, a powinien najpierw brać ten o mniejszym promieniu, więc dodałem, że jak iloczyn wektorowy jest równy, to liczy po odległości, usunąłem pierwiastek, żeby nie bawić się w double, a to i tak nic nie psuje.

Kod dający 100pkt, z sortowaniem kątowym i algorytmem Grahama:

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;
typedef long double ld;
typedef long long ll;

ll y_poczatkowy = 0, x_poczatkowy = 0;

struct Punkt
{
    ll y;
    ll x;
    ll idx;
    bool operator < (const Punkt &inny) const
    {
        if ((y - y_poczatkowy) * (inny.x - x_poczatkowy) == (inny.y - y_poczatkowy) * (x - x_poczatkowy))
            return (y - y_poczatkowy) * (y - y_poczatkowy) + (x - x_poczatkowy) * (x - x_poczatkowy) < (inny.y - y_poczatkowy) * (inny.y - y_poczatkowy) + (inny.x - x_poczatkowy) * (inny.x - x_poczatkowy);
        return (y - y_poczatkowy) * (inny.x - x_poczatkowy) < (inny.y - y_poczatkowy) * (x - x_poczatkowy);
    }
};

ll n = 0;
ll iloczyn_vectorowy = 0;
vector<Punkt> punkty;
vector<Punkt> dod;
vector<Punkt> otoczka_wypukla;
Punkt poczatkowy = {1000000000000,1000000000000,-1};
vector<ll> wyn_vect;

inline ll iloczyn_vect(Punkt p1, Punkt p2, Punkt p3)
{
    p2.x -= p1.x, p3.x -= p1.x, p2.y -= p1.y, p3.y -= p1.y;
    return p2.x * p3.y - p3.x * p2.y;
}

inline ll iloczyn_skal(Punkt p1, Punkt p2, Punkt p3)
{
    p2.x -= p1.x, p3.x -= p1.x, p2.y -= p1.y, p3.y -= p1.y;
    return p2.x * p3.x + p2.y * p3.y;
}

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

    cin >> n;
    punkty.assign(n,{});
    for (int i = 0; i < n; ++i)
    {
        cin >> punkty[i].x >> punkty[i].y;
        punkty[i].idx = i;
    }

    for (int i = 0; i < punkty.size(); ++i)
    {
        if (punkty[i].y < poczatkowy.y)
            poczatkowy = punkty[i];
        else if (punkty[i].y == poczatkowy.y and punkty[i].x < poczatkowy.x)
            poczatkowy = punkty[i];
    }
    y_poczatkowy = poczatkowy.y, x_poczatkowy = poczatkowy.x;

    for (int i = 0; i < n; ++i)
        if (punkty[i].idx != poczatkowy.idx)
            dod.push_back(punkty[i]);
    punkty = dod;
    sort(punkty.begin(), punkty.end());

    for (int i = 0; i < punkty.size(); ++i)
        punkty[i].y -= y_poczatkowy, punkty[i].x -= x_poczatkowy;

    poczatkowy.y = 0, poczatkowy.x = 0;
    otoczka_wypukla.push_back(poczatkowy);
    for (int i = 0; i < punkty.size(); ++i)
    {
        if (otoczka_wypukla.size() <= 1)
            otoczka_wypukla.push_back(punkty[i]);
        else
        {
            while(otoczka_wypukla.size() >= 2)
            {
                iloczyn_vectorowy = iloczyn_vect(otoczka_wypukla[otoczka_wypukla.size()-2],otoczka_wypukla[otoczka_wypukla.size()-1],punkty[i]);
                if (iloczyn_vectorowy <= 0)
                    otoczka_wypukla.pop_back();
                else
                    break;
            }
            otoczka_wypukla.push_back(punkty[i]);
        }
    }

    if (otoczka_wypukla.size() <= 2)
    {
        cout << otoczka_wypukla.size() << '\n';
        for (int i = 0; i < otoczka_wypukla.size(); ++i)
            cout << otoczka_wypukla[i].idx + 1 << '\n';
        return 0;
    }

    for (int i = 0; i < otoczka_wypukla.size(); ++i)
    {
        int idx_dalej = 0, idx_wczesniej = 0;
        if (i == otoczka_wypukla.size()-1)
            idx_dalej = 0;
        else
            idx_dalej = i+1;
        if (i == 0)
            idx_wczesniej = otoczka_wypukla.size()-1;
        else
            idx_wczesniej = i-1;
        if (iloczyn_skal(otoczka_wypukla[i],otoczka_wypukla[idx_wczesniej],otoczka_wypukla[idx_dalej]) >= 0)
            wyn_vect.push_back(otoczka_wypukla[i].idx);
    }

    cout << wyn_vect.size() << '\n';
    sort(wyn_vect.begin(), wyn_vect.end());
    for (int i = 0; i < wyn_vect.size(); ++i)
        cout << wyn_vect[i] + 1 << '\n';

    return 0;
}

A wgl kojarzysz jakieś zadania z geometri analitycznej, np. na otoczkę wypukłą z OI-a?