N-úhelník – C / C++ – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

N-úhelník – C / C++ – Fórum – Programujte.comN-úhelník – C / C++ – Fórum – Programujte.com

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
Huge0
Návštěvník
23. 1. 2007   #1
-
0
-

Zdravím, mám přibližně takovýto problém.
Jde o to, že máte zadáno n bodů - znáte jejich souřednice x,y,z.
No a úkolem je zjistit, zda leží na 1 přímce, a jestli ne, tak kolikaúhelník minimálně tvoří.
A to je právě ten problém. Myslel jsem, že vím, jak na to, ale když si vypočítám všechny úsečky, který obsahují více než 2 body, tak mi to vůbec nepomůže. Prostě nevím, proto prosím o pomoc. Mělo by to být v prostoru, ale ještě nevím ani, jak to udělat v rovině.
Dám vám jedno ukázkový zadání:



A 0 4 0
B 1 4 0
C 3 4 0
D 7 4 0
E 6 0 0
F 5 1 0
G 4 2 0
H 1 5 0
I 0 6 0

Tak se s tím zkušte nějak poprat, dík za pomoc.

Nahlásit jako SPAM
IP: ...–
Reklama
Reklama
bugy0
Návštěvník
23. 1. 2007   #2
-
0
-

To Huge:No ja bych to asi resil tak, ze bych pro kazde dva body napsal parametrickou rovnici primky v prostoru
x = AX + sX*t
y = AY + sY*t
z = AZ + sZ*t
a to v nějakým rozumnym "normalizovaným" tvaru (tatáž přímka lze popsat nekonečně mnoho zpusoby->kuprikladu tak, že sX bude vzdy rovno 1,pokud ovsem nebude 0 a sY a sZ prepocitat, to samé nějak udělat s absolutními souřadnicemi AX, AY, AZ, treba je prepocitat na hodnotu nejblizssi pocatku [0,0,0]).

Az tohle udelas dostanes n*(n-1)/2 primek, ktere vzajemne porovnas a pokud budes mit dve nebo vice primky stejny (no ono nejspis minimalne 3, pocet stejnych primek je umerny poctu bodu v primce lezicich podle vzorce m*(m-1)/2 ), tak vis ze lezi na primce

Az tohle dodelas, tak si zrekapitulujes, kolik mas primek s vice nez dvema bodama (napriklad dve primky s 3body a jedna s 5 body->minimalni n-uhelnik ma (n-2*1-3)úhlu

A jeste musis dat pozor, aby ti případný n-uhelnik (ktery ma alespon na jedne strane nejmene 3 ruzne body), respektive aby se jeho jednotlive strany nekrizil (nemeli zadny spolecny bod)-to by potom moc jako n-uhelnik nevypadalo, vypadalo by to spíše jak nekolik n-uhelniku se spolecnymi vrcholy, tudiz ten predchozi odstavec nemusi vzdy platit, tohle uz zacina byt krapet slozitejsi a popisovat to slovy je celkem tezky a ani nasledny analyticky reseni neni nejjednodussi, to by ale potom slo resit hrubou silou vypocetni kapacity pocitace.

asi by to slo resit i elegantneji, ale ted me nic nenapada

asi si to bude chtit trochu zopakovat Analytickou geometrii, aby jsi to naprogramoval :)

Nahlásit jako SPAM
IP: ...–
co takhle vyletět si na Měsíc ... mmm ... vomrknout jestli tam není náhodou vedle moře klidu taky moře něčeho rozumnějšího
ivanhoex
~ Anonymní uživatel
36 příspěvků
24. 1. 2007   #3
-
0
-

Mel bych napad:

1) setridit podle 1.,2.,3. Sloupce (X,Y,Z) qsort
2) vytvorit nove stejne velky 3xN pole
3) v kazdym hledat nejmene triprvkovou posloupnost a tu kopirovat do noveho (zatim nevim jak na to)
4)v novem poli jit po radcich a pocitat pro kazdy radek(pokud zde je aspon ve dvou sloupcich cislo) posloupnosti, pokud najdeme rovnou triprvkovou, konec, pokud nekolik, musime pozna kolika prvkova je, pak mame N-uhelnik

este poradne nevim, jak na naky ty casti, alepokud opravdu nevis, tak ti to trebas pomuze, snad je te postup aspon trochu spravnej, ale bude tam vysoka casova i pametova slozitost :(

este neco zkusim, ale je to na me dost tezkej priklad

Nahlásit jako SPAM
IP: ...–
bugy0
Návštěvník
24. 1. 2007   #4
-
0
-

To ivanhoex: tohle reseni je mozna lepsi, tim ze:
- pro kazde dva body urcis smernici (bod A a B)
- pak projedes postupne vsechny ostatni body a u kterych zjistis stejnou smernici (nebo jeji nasobek) k bodu A nebo B, tak tyto tri body lezi v primce
- pokud najdes 3 body lezici v primce, tak zkus jeste najit dalsi 4. bod lezici v teto primce, popripade 5. 6. atd.
- opet si vyhodnotis kolik mas 3 a vice "bodovych " primek a body, ktere by lezely, uprostred dvou vrcholy spocitas a n-uhlenik bude mit o to mene vrcholu
- jak jsem psal v predchozim prispevku, pokud takto "spojis strany(to je neco jako bys castecne urci poradi sousednich vrcholu v n-uhelniku" - tak ti pak nemusi vyjit smysluplny n-uhelni, nakresli si napriklad tento jednoduchy priklad v rovine:
A=[0,3]
B=[2,1]
C=[2,2]
D=[2,4]
E=[3,3]
--body BCD lezi v primce, bod C je mezi body BD ->nakresli n-uhelnik AB(C)DE->uvidis ze ti vyjdou jakoby dva trojuhelniky

Nahlásit jako SPAM
IP: ...–
co takhle vyletět si na Měsíc ... mmm ... vomrknout jestli tam není náhodou vedle moře klidu taky moře něčeho rozumnějšího
mad_nightmare
~ Anonymní uživatel
14 příspěvků
27. 1. 2007   #5
-
0
-

Vymyslel sem postup, na ktery, byt je vypocetne slozitejsi, coz by ale u tyhle ulohy nemuselo tolik vadit, staci pocitat pouze vzdalenosti bodu v prostoru.
Z mnoziny bodu B bych ubral dva libovolne a pridal bych ji do mnoziny vrcholu mnohouhlenika V
prosel bych zbyvajici body v B, estli nektery nelezi na spojnici dvou vybranych z V. takovy bych z mnoziny B odstranil
presunul bych nahodny bod z B do V
opet bych zjistil estli nelezi nektery bod z B na spojnici bodu z V (staci overovat pouze spojnice s poslednim pridanym)
takto bych postupoval dokud neni B prazdna, ve V pak jsou pouze vrcholy mnohohelniku

casova slozitost bude lepci nez kubicka :)

PSk tvemu zadani:

...lem je zjistit, zda leží na 1 přímce, a jestli ne, tak kolikaúhelník minimálně tvoří.



netvori nahodou vzdy prave jeden mnohouhlenik, jestlize nepocitas vrchol, lezici na spojnici dvou jinych jako vrchol?

Nahlásit jako SPAM
IP: ...–
Miroslav Kajan0
Věrný člen
27. 1. 2007   #6
-
0
-

To mad_nightmare:

netvori nahodou vzdy prave jeden mnohouhlenik, jestlize nepocitas vrchol, lezici na spojnici dvou jinych jako vrchol?


Myslím, že se ptal KOLIKAÚHELNÍK tvoří, nikoliv, že tvoří právě jeden mnohoúhelník.

Nahlásit jako SPAM
IP: ...–
Zápisky z dění na FB (momentálně ve vývoji): http://fbpd.ic.cz/
mad_nightmare
~ Anonymní uživatel
14 příspěvků
29. 1. 2007   #7
-
0
-


To mad_nightmare:

netvori nahodou vzdy prave jeden mnohouhlenik, jestlize nepocitas vrchol, lezici na spojnici dvou jinych jako vrchol?




Myslím, že se ptal KOLIKAÚHELNÍK tvoří, nikoliv, že tvoří právě jeden mnohoúhelník.



to byla reakce na slovo MINIMALNE a jak sem nad tiom premyslel, tak stejne asi chybna

Nahlásit jako SPAM
IP: ...–
Huge
~ Anonymní uživatel
57 příspěvků
3. 2. 2007   #8
-
0
-

To bugy: Snažíš se mi sice pomoct pěkně, ale to všechno už jsem věděl. Jsem asi ve stádiu, kdy mám zjištěný ty nulový vrcholy (kde je úhel 180°), ale nevím jak zjistit, že nevnikne paskvil, ale mnohoúhelník.
To mad_nightmare: Tvoje řešení se mi zdá trošku nefunkční, protože, když zahrneš náhodný bod, tak můžeš přehlédnout zretězení bodů se zanedbatelnými vrcholy, takže ti sice vyjde mnohoúhelník, ale ne MINIMÁLNÍ.

Nahlásit jako SPAM
IP: ...–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 103 hostů

Podobná vlákna

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý