Pont körül konvex négyszög

Fórumok

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!

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

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

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

"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

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