# Uvod u algoritme / Osnovni geometrijski algoritmi / PetougaoTestKonveks

**URL:** <https://algora.petlja.org/t/uvod-u-algoritme-osnovni-geometrijski-algoritmi-petougaotestkonveks/252>\
**Category:** Pitanja i problemi\
**Created:** [June 18, 2017, 12:46am UTC](https://algora.petlja.org/t/uvod-u-algoritme-osnovni-geometrijski-algoritmi-petougaotestkonveks/252 "2017-06-18T00:46:27Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![junka](https://algora.petlja.org/user_avatar/algora.petlja.org/junka/32/122_2.png) [@junka](https://algora.petlja.org/u/junka)\
**Post date:** [June 18, 2017, 12:46am UTC](https://algora.petlja.org/t/uvod-u-algoritme-osnovni-geometrijski-algoritmi-petougaotestkonveks/252/1 "2017-06-18T00:46:27Z")

</div>

Potrebna mi je pomoć, nikako ne uspevam da rešim zadatak: [http://bee.bubblecup.org/Problems/MnogougaoTestKonveks#problem](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;
}
```

---

<div class="post-metadata">

**Author:** ![Delta003](https://algora.petlja.org/user_avatar/algora.petlja.org/delta003/32/275_2.png) [@Delta003](https://algora.petlja.org/u/Delta003)\
**Post date:** [June 18, 2017, 12:47pm UTC](https://algora.petlja.org/t/uvod-u-algoritme-osnovni-geometrijski-algoritmi-petougaotestkonveks/252/2 "2017-06-18T12:47:27Z")

</div>

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:

> [@Osnovni geometrijski algoritmi](http://algora.petlja.org/t/osnovni-geometrijski-algoritmi/81):
>
> Autor: Nikola Milosavljević Sadržaj: Rastojanje izmedju dve tačke Jednačina kružnice Jednačina prave Pripadnost tačke duži Rastojanje izmedju tačke i prave Eksplicitni oblik prave Paralelnost pravih Normalnost pravih Presek dve duži Površina prostog poligona Skalarni prozivod Vektoriski prozivod [Preuzmite tekst](https://dms.rs/agogeit/data/dodatne_2009/Geometrijski%20algoritmi%20%5Bteorija%5D%20B.pdf)

---

<div class="post-metadata">

**Author:** ![Vugdelija](https://algora.petlja.org/user_avatar/algora.petlja.org/vugdelija/32/631_2.png) [@Vugdelija](https://algora.petlja.org/u/Vugdelija)\
**Post date:** [June 22, 2017, 8:40pm UTC](https://algora.petlja.org/t/uvod-u-algoritme-osnovni-geometrijski-algoritmi-petougaotestkonveks/252/3 "2017-06-22T20:40:52Z")

</div>

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)