Zadanie z otoczki wypukłej

Question

Witam, mam problem z zadaniem z otoczki wypukłej.

Treść: link

Problem: Pomoże ktoś z testami? Zauważyłem, że jeden test przekracza oczekiwaną odpowiedź, natomiast dwa pozostałe różnią się tylko o 1.

Testy: link

Kod: wklejony na dole posta

1. Na początku sortuje punkty względem odciętych, a w przypadku dwóch punktów o jednakowych odciętych - względem rzędnych, oczywiście niemalejąco.

2. Zaczynam od punktu skrajnego, tj. najbardziej wysuniętego na południowy-zachód i dodaje go do otoczki. To samo robię z drugim punktem z mojej posortowanej listy/wektora.

3. Dalej, zakładam, że każdy następny punkt będzie znajdował się na otoczce, a gdy okaże się, że następny znajduje się "po prawo" od prostej wyznaczanej przez 2 poprzednie punkty to "cofam się" aż do momentu, gdy ten sam punkt znajduje się "po lewo" od prostej wyznaczanej przez 2 poprzednie punkty.

4. Kontynuuje procedurę dopóki nie napotkam ostatniego punktu.

5. Robię to samo tyko dla górnej części, czyli od końca do początku pamiętając o tym, że nie mogę już zaliczać pierwszego i ostatniego punktu, gdyż zaliczyłem je już do otoczki podczas pierwszego etapu procedury.

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

using namespace std;

struct Pkt {
    long long x, y;

    bool operator < (const Pkt &pkt) const {
        if (x == pkt.x)
            return (y < pkt.y);
        return (x < pkt.x);
    }
};

vector <Pkt> pkt;
vector <Pkt> otoczka;

long long ilo_wek(Pkt A, Pkt B, Pkt C) {
    return ((C.x-A.x)*(B.y-A.y) - (B.x-A.x)*(C.y-A.y));
}

void buduj_otoczke(int n) {
    otoczka.push_back(pkt[0]);
    otoczka.push_back(pkt[1]);

    int k = 1;
    for (int i = 2; i < n; i ++) {
        while (k > 0 and ilo_wek(otoczka[k - 1], otoczka[k], pkt[i]) > 0) {
            k --;
            otoczka.pop_back();
        }
        otoczka.push_back(pkt[i]);
        k ++;
    }

    for (int i = n - 2; i > 0; i --) {
        while (k > 0 and ilo_wek(otoczka[k - 1], otoczka[k], pkt[i]) > 0) {
            k --;
            otoczka.pop_back();
        }
        otoczka.push_back(pkt[i]);
        k ++;
    }

    cout << k + 1 << '\n';
    for (auto a : otoczka)
        cout << a.x << ' ' << a.y << '\n';
}

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

    int n;
    cin >> n;

    for (int i = 0; i < n; i ++) {
        long long x, y;
        cin >> x >> y;

        pkt.push_back({x, y});
    }

    sort(pkt.begin(), pkt.end());

    buduj_otoczke(n);
}

 

Answer 1

Zobacz taki test:

4
0 1
0 2
0 3
0 4

 

Comments

Widze duplikaty punktów ...

Ale to w takim razie ten algorytm do kosza, czy może jakaś poprawka?

Widziałem na internecie, że ludzie ogólnie to sortują kątowo od wybranego punktu, a reszta taka sama jak u mnie, czyli sprawdzanie czy następny pkt jest "po prawo" [...]. Może właśnie przerzucić się na taką metodę?

---

Można i tak i tak zrobić. Tu masz obie wersje. Z czego ta która sortuje kątowo ma chyba trochę prostszy kod

Answer 2

Otrzymałem już 100% za to zadanie. Dodałem takie 2 linie po 2. forze:

while (k > 0 and ilo_wek(otoczka[k - 1], otoczka[k], pkt[0]) > 0)
            k --, otoczka.pop_back();

Ogólnie chodzi o to, żeby sprawdzić poprawność ostatniego punktu otoczki z pierwszym punktem, bo może być taka sytuacja na przykład:

No i na to trzeba zwrócić uwagę.

 

Tak czy siak, dzięki za poświęcony czas, miłego dnia :D