Sziasztok!
A következő algoritmushoz szeretnék segítséget kérni: Adott egy P ponthalmaz és egy q pont. Adjuk meg a ponthalmaz 4 olyan pontját, hogy azok konvex négyszöget alkotnak amely tartalmazza a q pontot, de a ponthalmaz egyetlen másik pontját sem.
Ezt kellene megoldanom O(n)-es algoritmussal. Ha háromszöget találok (aminek akár az oldalára is eshet a pont), akkor onnan megvan az algoritmus.
Olyasmire gondoltam, hogy a pontokat kellene rendezni a q-tól való távolságuk és szögük szerint, és az egy egyenesre esők közül csak a közelebbieket tartanám meg. Innen viszont nincs sok ötletem.
Köszönöm előre is!
- 2090 megtekintés
Hozzászólások
Időben kezded, ma éjfél a határidő.
(ha nem tévedek, és te is SZTE-s vagy)
ps: a múltkori egyenessel vaó lefedéses feladatnak felrakom a megoldását, a hátáridő után.
Petya
- A hozzászóláshoz be kell jelentkezni
Ha jol gondolom, akkor sikerult megoldanod a feladatot helyesen.
Remelem segitet a mulkori brejnsztorm valamit.
Milyen idok jottek ki a megoldasokra ?
g
- A hozzászóláshoz be kell jelentkezni
Hello!
Nem lett tökéletes, de a 14 tesztesetből 9-re jó, és a többinél sem időtúllépéssel, hanem rossz eredmény miatt áll meg. A legnagyobb inputra (90000 pont) 0.118 mp alatt lefut. Vannak olyan esetek, amik lefedhetőek, de mégis azt írja rá, hogy nem. Nem lehet nagy baja. de nincs túl sok időm foglalkozni vele. A követelményt így is bőven teljesíti.
Petya
- A hozzászóláshoz be kell jelentkezni
Az jo, a lenyeg, hogy meg lett.
Gratulalok.
- A hozzászóláshoz be kell jelentkezni
O(n)-es algoritmust erre?
hmmm... ez Szívatás, nagy Sz-szel.
ami át van húzva, azt teljesen fölösleges elolvasni. az olyan, mintha ott sem lenne
- A hozzászóláshoz be kell jelentkezni
Nem szivatas csak egy HGY feladat. Nezd meg a Petya hasonlo topikjat.
Ott van egy ehhez hasonlo feladat megoldassal. Az is O(n)-es feladat.
- A hozzászóláshoz be kell jelentkezni
"Nem szivatas csak egy HGY feladat. Nezd meg a Petya hasonlo topikjat.
Ott van egy ehhez hasonlo feladat megoldassal. Az is O(n)-es feladat."
de.
gondolkozz.
_Petya_ másik topikja a ponthalmaz-lefedéses? nem mondod! ez most komoly? naháááát, észre sem vettem...
pl. egyenes szakaszokkal síkbarajzolt K_4 és q a belsejében, erre hogy működik a milyen algoritmusod? Vagy q minden koordinátája negatív, a többi pont minden koordinátája pozitív. Na akkó' mi va'? :D
Ha van is egyáltalán O(n)-es algoritmus a konvex 4szöges feladatra, akkor sem egy triviális eljárás lesz, vagy ha az, akkor meg irtó nehéz igazolni a bonyolultságát. (még az O(n**4) sem triviális, de azt már látom)
ami át van húzva, azt teljesen fölösleges elolvasni. az olyan, mintha ott sem lenne
- A hozzászóláshoz be kell jelentkezni
Gondolkozz, aztan szovegelj. Ez a feladat 4. eves hallgatoknak
lett feladva es gondolom mar az evek alatt sokan megoldottak.
En most nem erek ra ezzel foglalkozni, de mivel HGY adta fel,
biztos vagyok benne, hogy nem csak egy trefa a feladat.
g
- A hozzászóláshoz be kell jelentkezni
Megcsinalod a ponthalmaz delaunay-haromszogeleset, igaz ez ordo(n*log(n)) ido", de ha ez megvan, akkor ma'r csak vegig kell menni a haromszogeken (osszesn kb 2n-k haromszog van, ahol k a ponthalmaz konvex burkan levo" pontok szama; tehat ordo(n)-ben vegig lehet nezni oket) es meg kell nezni melyikbe esik bele.
nem emlekszem mar pontosan a reszletekre, de a divide & conquer algoritmusnal, amennyiben adott egy ponthalmaz konvex burka, es a te kerdeses pontod benne van ebben a burokban, es csak ezt a burkot bontod tovabb, akkor lehet hogy le lehet menni ordo(n) ido"re. hogy egy pont benne van-e egy k ponttal megadott, konvex sokszogben, azt ordo(k) ido" alatt el lehet donteni, viszonylag egyszeru"en (gyk. minden i-re q-p[i] es a p[i+1]-p[i] (ahol p[k+1]=p[1]) vektorok kulso" szorozata azonos elo"jelu" kell, hogy legyen).
- A hozzászóláshoz be kell jelentkezni
Köszönöm az ötletet! Sajnos megvalósítani már nem maradt időm, majd jövőre. (Lehet hogy nem ma délután kellett volna elkezdeni?)
- A hozzászóláshoz be kell jelentkezni