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

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

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 :)

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

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

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ří.

To mad_nightmare:

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

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 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Í.