Geometria (Pascal)

Asi trochu náročnejšie zadanie - netreba mi zdroják, len všeobecný postup...

Je daných N bodov (každý s x, y). Treba vypočítať obsah najmenšieho vypuklého mnohouholníka (t.j. žiadny uhol nie je väčší 180), ktorý obsahuje všetky všetky body. Už mám algoritmus na výpočet obsahu trojuholníka z troch bodov, len ako to pospájať...

Mimochodom, skúšal som to takto:
nájsť najvýchodnejší a najzápadnejší bod, nájsť body nad a pod touto priamkou (najviac vľavo a vpravo), z toho boli 2 4-uholníky, vypočítať obsah, potom určiť nové severné a južné hranice a postupne to celé zužovať. Len je to dosť komplikované (aj to tak znie) a nefunguje to...možno na to ešte nemám vedomosti (prvák gym.).

hh vypukly to myslis ako konvexny?
a mnohouholnik je kolko uholnik? aj trojuholnik? pretoze ked mas viac uhlov tak mas zvycajne aj viac povrchu toho utvaru, vacsinou to tak byva.

taky spolahlivy sposob je ten ze si vypocitas obsahy vsetkych a postupne budes hladat ten konvexny od najmensieho mnohouhloveho uholnika.
ale aj tak ten s najmensim obsahom je trojuholnik.(teda aspon som sa s inym nestretol).
a ked ziadny uhol nieje vacsi ako 180 to znamena ze sa moze rovnat 180° ? potom by to nemusel byt trojuholnik.

Myslíš, že by to mal byť trojuholník? Menšie by sa nedalo?

Keď, tak si to pozrite...(to nedoriešené je g (a keďže má byť vrcholov 6, tak to evidentne nebude trojuholník)): http://zenit.gjh.sk/06.htm

nie je to tazka uloha, staci najst konvexny obal danej mnoziny, na wiki napriklad je na to algoritmus gift wrapping algorithm
zistovat, ci dany vrchol je "napravo" od danej priamky ... napriklad dosadenim do rovnice polroviny/priamky
ak H[i] su body body na hranici obalu, v poradi
zistit obsah konvexneho utvaru ... cez elementarne trojuholniky napr. vektorovym sucinom ... scitat obsah trojuholnikov (P[0],P[i],P[i+1])