Uvod u algoritme / Osnovni geometrijski algoritmi / PetougaoTestKonveks

Pitanja i problemi
1

Potrebna mi je pomoć, nikako ne uspevam da rešim zadatak: http://bee.bubblecup.org/Problems/MnogougaoTestKonveks#problem

Ispod je moje rešenje, u njemu pokušavam da pratim promenu nagiba susednih duži, ali ne prolazi testiranje. Bilo koji test primer koji sam uspem da smislim prolazi, pa mora biti da nešto previđam? Da li se tačka i prava računaju kao konveksni poligoni?

#include <iostream>
#include <vector>

using namespace std;

struct Point {
    double x;
    double y;
};

static int sign(double d)
{
    return d == 0 ? 0 : d > 0 ? +1 : -1;
}

int main()
{
    constexpr int kNumPoints = 5;
    vector<Point> points(kNumPoints);

    for (int i = 0; i < kNumPoints; i++) {
        cin >> points[i].x;
        cin >> points[i].y;
    }

    int lastSign = 0xDEC0'0'0;

    for (size_t i = 0; i < points.size(); i++) {
        auto p1 = points[i];
        auto p2 = points[(i + 1) % points.size()];
        auto p3 = points[(i + 2) % points.size()];

        auto dx1 = p2.x - p1.x;
        auto dy1 = p2.y - p1.y;
        auto dx2 = p3.x - p2.x;
        auto dy2 = p3.y - p2.y;

        if (auto t = dy1 * dx2 - dy2 * dx1) {
            if (lastSign > 1) {
                lastSign = sign(t);
            } else if (lastSign != sign(t)) {
                cout << "NE";
                return 0;
            }
        }
    }

    cout << "DA";
    return 0;
}
2

Uvek ti je dato 5 razlicitih tacaka, tako da slucaj tacke i prave ne moras da razmatras.
Na prvi pogled, formula koju koristis da proveris skretanje nije dobra.
Treba da posmatras vektore p1p2 i p1p3, a ne p1p2 i p2p3.
Ovde mozes da procitas vise o tome kako se dolazi do ove formule i da vidis gde gresis:

3

Meni se čini da si bio blizu kada si pominjao prave.
Malo sam tražio po vikipediji (engleski, srpski), i definicije poligona, konveksnosti i sl. nisu konzistentne, tako da ćemo morati da popravimo (preciziramo) postavku zadatka. U ovom zadatku se pretpostavlja da uglovi mnogougla mogu biti bilo koje veličine, između ostalog i opruženi (i neki možda još čudniji). Konveksnost se koristi u smislu sledećih definicija:

Skup tačaka je konveksan akko za bilo koje dve tačke A i B tog skupa, svaka tačka duži AB takođe pripada skupu.
Poligon je konveksan akko je skup tačaka tog poligona konveksan.
(akko znači ako i samo ako)