| | |
| Stránka: 1 z 1
| [ Príspevkov: 5 ] | |
Autor | Správa |
---|
Registrovaný: 25.06.08 Prihlásený: 13.10.10 Príspevky: 30 Témy: 10 | Napísal Soso: 25.06.2008 13:57 | |
|
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.).
|
|
Registrovaný: 16.05.07 Prihlásený: 01.08.17 Príspevky: 837 Témy: 6 | Napísal juho: 25.06.2008 14:52 | |
|
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.
_________________ getch();?{readkey;?} na konci? !A naco! Riesenie je (Alt+F5)
99% pochopí a shaggy je druhá kategória |
|
Registrovaný: 25.06.08 Prihlásený: 13.10.10 Príspevky: 30 Témy: 10 | Napísal autor témy Soso: 25.06.2008 15:02 | |
|
Myslíš, že by to mal byť trojuholník? Menšie by sa nedalo?
_________________ "Civilizácia sa rozvíja nárastom počtu dôležitých úkonov, ktoré môžeme vykonávať bez predchádzajúcej úvahy."
Alfred North Whitehead |
|
Registrovaný: 25.06.08 Prihlásený: 13.10.10 Príspevky: 30 Témy: 10 | Napísal autor témy Soso: 25.06.2008 18:16 | |
|
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
_________________ "Civilizácia sa rozvíja nárastom počtu dôležitých úkonov, ktoré môžeme vykonávať bez predchádzajúcej úvahy."
Alfred North Whitehead |
|
Registrovaný: 26.06.08 Prihlásený: 26.06.08 Príspevky: 1 Témy: 0 | Napísal lmiki: 26.06.2008 13:41 | |
|
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])
|
|
| Stránka: 1 z 1
| [ Príspevkov: 5 ] | |
Podobné témy | Témy | Odpovede | Zobrazenia | Posledný príspevok |
---|
| Geometria v Vzdelanie, štúdium, škola | 16 | 1682 | 04.01.2009 22:50 pepek.namornik | | Zla geometria - vplyv na napravu v Automobily, motorky | 6 | 1658 | 07.04.2017 16:09 Cirky | | Free Pascal a Turbo Pascal v Assembler, C, C++, Pascal, Java | 0 | 381 | 19.12.2014 13:18 Styracoz | | pascal... v Assembler, C, C++, Pascal, Java | 5 | 901 | 18.10.2008 19:02 redog | | Pascal v Assembler, C, C++, Pascal, Java | 7 | 625 | 09.10.2011 21:30 F3RY | | Pascal [ Choď na stránku: 1, 2 ] v Assembler, C, C++, Pascal, Java | 40 | 1448 | 11.12.2016 22:08 viki | | pascal v Assembler, C, C++, Pascal, Java | 2 | 1101 | 09.03.2007 14:08 misolax | | Pascal v Assembler, C, C++, Pascal, Java | 7 | 822 | 14.05.2011 20:04 F3RY | | pascal v Assembler, C, C++, Pascal, Java | 2 | 566 | 24.06.2010 20:17 KatjushaMan | | Pascal v Assembler, C, C++, Pascal, Java | 4 | 2031 | 01.03.2018 8:02 MTK | | pascal v Assembler, C, C++, Pascal, Java | 6 | 727 | 08.01.2009 17:45 majka090 | | pascal v Assembler, C, C++, Pascal, Java | 11 | 1282 | 07.04.2007 16:50 programator | | pascal v Assembler, C, C++, Pascal, Java | 19 | 3054 | 30.04.2007 19:54 nikita | | pascal v Assembler, C, C++, Pascal, Java | 0 | 698 | 03.05.2009 12:35 ebb | | FREE PASCAL v Assembler, C, C++, Pascal, Java | 1 | 876 | 25.09.2010 12:19 Goergius | | Pascal zaznam v Assembler, C, C++, Pascal, Java | 1 | 345 | 28.04.2014 18:41 Ďuri |
| Nemôžete zakladať nové témy v tomto fóre Nemôžete odpovedať na témy v tomto fóre Nemôžete upravovať svoje príspevky v tomto fóre Nemôžete mazať svoje príspevky v tomto fóre
|
|