Ponthalmaz lefedési probléma

Algoritmusok

Hello!

A segítségeteket kérném, a feladat: megadni egy adott ponthalmazt lefedő 3 egyenest (vagy ha nem lehet 3 egyenessel lefedni, akkor ezt jelezni), mindezt O(n) időben. Arra gondoltam, konvex burkot kellene számolni, és talán abból valahogy ki lehet indulni, de ez csak ötlet.

Köszönöm a segítésget előre is!

Petya

  • 7481 megtekintés

( apal v | 2007. 04. 08., v – 00:12 )

Hat, egy egyszeru megoldas az az, hogy O(n*log(n)) ido"ben meghatarozod a ponthalmaz Delaunay-haromszogele'se't, majd ebbo"l szarmaztatod a konvex burkot (azaz azon pontok halmaza't, melyek nem teljesen koruljarhatoak), ez pedig O(n) ido"ben tuti megvan, amennyiben a haromszogelesi info adott. A wikipedia: konvex burok szerint viszont enne'l jobb ido"ben nem lehet meghatarozni, vagyis O(n*log(k)) ido"re le lehet vinni, ahol k a burok pontjainak sza'ma, de ez altalanos esetben sqrt(n), azaz O(n*log(sqrt(n))=O(n*log(n)/2)=O(n*log(n)), lenyegeben ugyanaz.

A delaunay-haromszogelesre van progim (c-ben), a divide & conq modszer, minden jarulekos infoval egyutt, abbol csak meg lehet ma'r egyszeru"en csinalni konvex burkot (vagy direkte a 3 lefedo" egyenest), de arra nem tudok progit hirtelen.

A.

( gthomas | 2007. 04. 08., v – 07:02 )

Nem teljesen értem a feladatot:
- síkban adott egy ponthalmaz,
- ennek keressük lefedését 3 egyenessel
Nekem ez azt jelenti, hogy találjunk minél több pontot lefedő egyeneseket (kollineáris pontokat).

Viszont a fenti válaszból illetve a konvex burok keresésből arra következtetek, hogy a "lefedés" itt határolás, tehát 3 egyenessel akarjuk határolni a ponthalmazt, és ezek illeszkedjenek pontokra ???

Hat, gondolom az a kerdes, hogy keressu"k meg a legkisebb (teruletu", keru"letu", linearis meretu", ...) haromszoget, ami minden pontot tartalmaz. Ha megvan a konvex burok, akkor relative egyszeru" erre felso" becselest adni (konvex burok kore' irt ko"r ko"re' irt szabalyos haromszog pl. megfelelo" e celra, es ezt azutan lehet csokkenteni, hogy rahuzni valahogy a legkozelebbi pontokra vagy mi).

Egyszerűen az a feladat, hogy van n darab különálló pont a síkon, és ezek lefedhetők-e 3 db egyenessel, a terület, kerület stb lényegtelen. Tehát nem a ponthalmaz köré írható háromszöget kell keresni, hanem 3 olyan egyenest, amelyeken az összes pont rajta van. Ha 3 egyenes nem elég a pontok lefedéséhez, akkor azt kell visszaadni, hogy nincs megoldás. Lehet, hogy félreérthetően fogalmaztam meg a feladatot.

Köszönöm az eddigi segítséget mindenkinek!

Petya

Mit jelent az, hogy lefedni pontot egyenessel?

Úgy értjük, hogy a pontjaink adva vannak az euklideszi síkon fejenként 2 lebegőpontos koordinátával, és keresünk olyan egyeneseket, amik valamilyen közelségben mennek el a pontok mellett (lebegőpontos számítási hiba miatt ugye pontos illeszkedés kizárva)? A kérdés, hogy összesen 3 egyenes elegendő-e a teljes ponthalmaz lefedésére?

Mi a gyakorlati jelentősége ennek a feladatnak?

Tehát keressünk maximális kollinearitásokat, amik együtt lefedik a ponthalmazt.

Bármely két ponta illeszthető egyenes, ellenőrizni lehet, hogy van-e még pont, ami szintén illeszkedik az adott egyenesre.
Ez (n alatt 2) lehetséges egyenes, egyenesenként n-2 ellenőrizendő pont.

Így kapsz halmazokat, amiket lefed egy-egy egyenes. A kérdés az, hogy van-e legfeljebb 3 olyan, melyekben minden pont benne van (uniójuk a teljes halmaz), vagy semelyik 3 halmaz uniója sem adja ki az alaphalmazt - ellenpélda.

Biztos, hogy ez a leglassab megoldás, de megoldás. Optimalizálni lehet, de szvsz az ellenpélda (nincs fedés) csak így mutatható meg.

Egyben válaszolok mindenre :)

A koordinátk egészek, így lehet pontos illeszkedés.

A fenti algoritmus egyértelmű, csak lassú. O(n) idejű algoritmust keresek a problémára. A fenti algoritmus ha jól nézem, minimum O(n^2)-es

A kérdés, hogy összesen 3 egyenes elegendő-e a teljes ponthalmaz lefedésére?

Igen, pontosan ez a kérdés.

Petya

( turul16 v | 2007. 04. 08., v – 13:06 )

Tipp:
Az ilyen jellegű problémák megoldása, olyasmi szokott lenni, hogy megnézzük szomszédos pontokhoz milyen meredekségű/szögű szakasz tartozik (pl. csak lentröl felfelé haladva), és ezt rendezzük valahogy, aztán ebböl probálunk egyeneseket vadászni.

Hirtelen ennyi jutott eszembe, ilyesféle irányba probálkoznék elsőre.

Nyilván nem azért megy az ember egyetemre/főiskolára, hogy megtanuljon valamit...
Megbocsássatok, de ilyesmit olvasva örül a szívem, hogy tandíjat kell fizetni.

Ez lehet, hogy eltés perverzitás, de nekem tetszik a feladat, végre nem egy adatbáziskezelés, meg n királynő, meg hasonló lerágott csontok.

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee."
-- Ted Ts'o

Akkor te vagy nagyon penge vagy, vagy rossz suliba mentél.
Én inkább az utóbbira szavazok. :)
(Nem általában rossz, csak neked rossz.)

Szerintem túl sok 3-5 év arra, hogy végigalibizzük, miközben értelmes dolgokat is lehetne tanulni. Persze értelmes dolgokat tanulhat az ember önszorgalomból is, csak akkor az rengeteg óra amit az iskolával tölt el, lényegében teljesen felesleges.

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee."
-- Ted Ts'o

Hja, akkor pont akkor hagytad abba, mikor kezd érdekes lenni.
De tényleg, első 3 évben igazán csak alapozó, többnyire száraz tárgyak vannak, alig 1-2 érdekes. Persze ha az ember keres azért már akkor is találhat érdekes speciket.
De a sávok már tényleg jók (feltéve hogy olyat választasz ami érdekel).

"azert matekot tanultam ott eleg sokat, kerdes mire jo az nekem
bar karomra sem valt valoszinuleg"
Hát, ez az elte. Azért ad egy olyan rálátást a dolgokra, hogy különösebben nem jösz zavarba, ha egy komolyabb tudományos cikk kerül eléd.

Más kérdés, hogy ez mennyire hasznos. Kis tulzással elég lenne 1 évig php-t meg java-t, C-t tanulni, mert a programozók 80% megél ennyiből.

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee."
-- Ted Ts'o

szerintem tok hasznos az, h ennyi matekot tanulunk.

en 4. felevet tolom, de hala az analizis/numerikus analizisnek,
tok jol elvagyok a munkahelyemen a kepfeldolgozasos problemakkal,
illetve a veges testek tudassal tudtam irni FEC enkodert..

szoval hasznos.

persze hobbi php koder minek jon egyetemre...

en vagyok a hobbi php koder?
tudom mit tettel tavaly(elott) nyaron kedves NagyZ ugy vigyazz...
engem - mint a keves magyar egyiket az ffmpeg-develen - kerdezgettel emailben az ffmpeg-rol.
de latom most mar nagyon megokosodtal :)

szerk: ujraolvasva valoszinuleg nem engem titulaltak hobbi php kodereknek, de mindegy
(azokkal amugy mi a baj?)

- Use the Source Luke ! -

Nincs a hobbi php kóderekkel semmi gond, amíg megmaradnak a php kódolásnál, és nem adják elő, hogy az egyetem semmire sem jó, hiszen ők a php-ből simán megélnek.
Sőt, kell is a php kóder, hogy pl nekem ne kelljen php kódokat írnom napszámban. :)

Nade kérlek, ha te egy ffmpeg fejlesztő vagy, ugyan mond már meg nekem, hogy hogyan tudnál Wawelet illetve Fouriere alapú formátumokhoz en- és dekódert írni, postprocessing filtert kódolni analízis, numerikus-analízis, és linalg nélkül?
Persze nyilván lehet úgy is, leírás alapján, miközben csak félig érted, de azért én reménykedem, hogy az ffmpeg nem így készül...

(Arról nem beszélve, hogy azokat is képezni kell valahol, akik a formátumokat kitalálják. Egyetem tehát kell, és hasznos (bár nem feltétlen tökéletes). Az más kérdés, hogy mindenkinek kell-e diploma. Aki csak php kódolásból akar megélni, és más nem is érdekli annak tényleg felesleges)

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee."
-- Ted Ts'o

jol van, latom egyesek ugy erzik az mar egy felsobb embertipus aki elvegzett egy egyetemet :)

valamilyen kepzesre termeszetesen szukseg van, ennyiben hasznos az egyetem, de ahogy irod a jelenlegi rendszer nem tokeletes, szerintem tavolrol sem. van esetleg par jo targy, de rengeteg dolgot csak be kell magolni es azt par het utan az ember ugy elfelejti mint a sicc. agytreningnek jo, de sok ertelme nincs.

- Use the Source Luke ! -

"jol van, latom egyesek ugy erzik az mar egy felsobb embertipus aki elvegzett egy egyetemet :)"

Attól nem lesz valaki felsőbb embertípus, hogy végigpuskázza a zh-kat, és elkéri más beadandó feladatait.
Attól lesz valaki felsőbb embertípus, hogy a szakmáját professzionális szinten végzi. Ez a szakma aztán lehet kőművestől kezdve bármi.

A hobbi php kódereben nem a php-n van a hangsúly, inkább a hobbi-n.
Mindössze azért php van ott, mert tapasztalataim szerint a webprogramozás területén van a legtöbb kókler...
(Nem, nem azt mondom, hogy önszorgalomból nem lehet professzionális szintre fejlődni, sőt azt mondom, hogy csupán az egyetemre támaszkodva nem lehet.)

"valamilyen kepzesre termeszetesen szukseg van, ennyiben hasznos az egyetem, de ahogy irod a jelenlegi rendszer nem tokeletes, szerintem tavolrol sem. van esetleg par jo targy, de rengeteg dolgot csak be kell magolni es azt par het utan az ember ugy elfelejti mint a sicc. agytreningnek jo, de sok ertelme nincs."

Üdvözöllek a porosz iskolarendszerben.
De pl az elte első 3 éve nem fölösleges annyira, mint amennyire akkor látszik, mikor tanulod. Egy csomó utált, és feleslegesnek tartott tárgy anyaga visszaköszön sokkal érdekesebb környezetben. Pedig én csak 4 sávot csinálok. Nyilván a még mindig értelmetlennek tűnő tárgyak ismeretanyagának is van szerepe más sávokban.

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee."
-- Ted Ts'o

1:
Bevprog a legfontosabb tárgyak egyike. A ciklus levezetési szabálya már önmagában is csodálatos, ha egy kicsit is ráérzel sose írsz rossz, illetve végtelen ciklust (csak ha akarsz :) ).
És még sorolhatnám...

2:
Hogy oktatnád a PP-t bevprog nélkül, vagy a prog. mód. elm.-et?
A sehogy nem válasz. (Ja, ha Vargánál végezted a progmódot, akkor elfogadom a választ, és mélységesen sajnállak).

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee."
-- Ted Ts'o

PP az tenyleg a legertelmetlenebb targyak egyike, HZ pofajatol meg hanyok :)
de nem ezt akartam irni, hanem azt, hogy sok mindenben egyetertunk,
par dologot meg nyilvan maskepp latunk, hiszen te meg oda jarsz es ezeket kell tanulnod,
en viszont mar otthagytam harom (esetemben negy) ev utan

- Use the Source Luke ! -

Van egy olyan összefüggés, hogy mindenki azt utálja, ami nem megy neki.
Kivételek persze vannak, én pl szeretem az analízist, pedig nem mondanám, hogy jó vagyok benne...
Numanal első félévét meg mindig gyűlöltem, pedig simán levizsgáztam belőle.

Az igazsághoz hozzátartozik, hogy az első 3 évben én is sokat szenvedtem. Formális nyelvek, számhálók, valszám, statisztika... Utáltam őket.
Az egésznek akkor kezd értelme lenni, mikor felveszed a sávokat. Feltéve hogy olyat veszel fel ami érdekel. Nyilván később jövedelmező lehet egy közgáz, vagy egy adatbázis sáv, de ezektől kiráz a hideg.
Úgyhogy csak magamat tudom ismételni, hogy pont a lényeg előtt hagytad abba.

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee."
-- Ted Ts'o

bevprog egy baromság.
Helyette jó kis tömény matematikus számtudot, matlogot, halmazelméletet, bonyolultságelméletet kéne tanulniuk, hogy valóban megértse minden program{ozó|tervező}, hogy miért kerül(t ) a matematikus részstring postfix abba a nyüves(téem) diplomájába.
ami át van húzva, azt teljesen fölösleges elolvasni. az olyan, mintha ott sem lenne

"bevprog egy baromság."
Na most meggyőztél... Meghajlok az érveid előtt...

"Helyette jó kis tömény matematikus számtudot, matlogot, halmazelméletet, bonyolultságelméletet kéne tanulniuk..."
Persze lehetne. Mondjuk már így is igaz, hogy a progmatosoknál több matekot szinte csak a matematikusok tanulnak. Egyrészt tehát az a bizonyos postfix nem véletlen, másrészt 3+2 évbe nem ártana beleférni.
(Az anyag már így is annyi, hogy a hallgatók többsége most sem fér bele.)
Programozásból/informatikából is lehetne még ennél többet is tanulni, az átlag munkahelyen meg már ennek is csak töredékét hasznosítja az ember.

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee."
-- Ted Ts'o

Ja, hogy 4. _félév_. Hihetetlen, hogy ennyi idő után sem tudom megszokni. :)

Szigorlathoz sok sikert. Én hihetetlen peches voltam, és párszor megszívtam. (Más szó nincs arra, hogy a kb 40-50 tételből 4-et nem tudtam, 4 tételt kaptunk, ebből 2 volt "rossz". Ha rám hallgatsz, minden mást félreraksz, minél hamarabb vizsgázol, hogy ha esetleg megszívod, legyen időd ismételni.)

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee."
-- Ted Ts'o

Se szigorlat előtt, se utána nem volt gondom anallal.
Vizsgák 4-es körül, gyakjegy 3. Szigorlatot mégis megszívtam. Más műfaj. Nem nehéz, csak rohadt sok. Kell hozzá egy kis szerencse is.

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee."
-- Ted Ts'o

( gabor2 | 2007. 04. 08., v – 15:11 )

Azert nem olyan nehez ez, tessek gondolkodni. Tavaj ue a feladatot a Moszka terol a Jaszaig oldottam meg a villamoson.

-Hogyan tudod osztalyozni a pontok halmazat ?
-Mivel tudod gyorsan eldonteni, hogy 3 pont egy egyenesen van (egesz szamok) ?
-Hogyan tudod gyorsan kiszamolni, hogy egy pont melyik osztalyba kerul ?
-Hany pontot kell beolvasnod minimum, hogy meghatarozd a halmazokat ?

Tobbet nem segitek.

g

Hello!

Ebből nekem nem nagyon jut eszembe semmi. A 3 pont egy egyenesen van-e az talán, hogy felírom két pontból az egyenletét, és ha a harmadik pont is rajta van, akkor oké, különben nem...

Hogyan kellene osztályoznom a pontokat?

Minimum talán a 6 pont, a lejjeb található leírás alapján?

Petya

Geométered vedd elő...
A négzet átlóin rajta van a négzet közepe. Ha mégsem, akkor újrajárom a geometria sávórákat.

Nem nullkarakterisztikájú, nem test az a modulus, amiben vagyunk, legalábbis kötve hinném, hogy a topiknyitó pl. ASCIIz-ként tárolná a pontok koordinátáit, tetszőleges abszolútértékű egészeket használva...

Minden bizonnyal "egy négyzet 3 különböző csúcsát alkotó ponthármas"-t akartál írni.

ami át van húzva, azt teljesen fölösleges elolvasni. az olyan, mintha ott sem lenne

talán ha megnéznéd, hogy mi a feladat, meghogy mi a leggyakoribb egész típus. A mezei egységsugarú programtervező informatnök hallgató rögtön egy gyári módon beállított cöcövel esik neki, ezt egy banános sörbe' lefogadom. És igen, tudom, hogy nem ilyen szőrösszívűek többnyire a beadandók tesztelése terén a tanerők, de kulturáltabban is lehet ellenőrizni a kollinearitást.

ami át van húzva, azt teljesen fölösleges elolvasni. az olyan, mintha ott sem lenne

A feladat itt látható leírásában egy büdös szó nincs a lehetséges bemeneti intervallumról. Ennyit a feladat megnézéséről.

Nyilván a feladat eredeti szövegét te sem ismered.

Az meg nem von le semmit a képlet értékéből, hogy te a naív implementációt (és tegyük hozzá, hogy a programnyelvek egy bizonyos halmazát) feltételezted, és rámutattál, hogy gond lehet.

Egyébkét kiváncsian várom a te kollinearitás ellenörzésed, de ezek után olyan módszert mondj, hogy én ne tudjak olyan rendszer, programozási nyelv, input adat 3-ast mondani, hogy ne adjon hülyeséget.

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee."
-- Ted Ts'o

"Nem nullkarakterisztikájú, nem test az a modulus, amiben vagyunk, legalábbis kötve hinném, hogy a topiknyitó pl. ASCIIz-ként tárolná a pontok koordinátáit, tetszőleges abszolútértékű egészeket használva..."

A képlet egész (sőt valós) számokra jó, a többi már implementációs kérdés...

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee."
-- Ted Ts'o

-Hogyan tudod osztalyozni a pontok halmazat ?
Ha igaz az allitas, hogy 3 egyenessel lefedheto a ponthalmaz, akkor
nyilvanvaloan 3 osztalyba szethetedet szet a pontok halmazat. Azaz barmelyik
3 elemet az egyik halmazbol kiveszed akkor azok egy egyenesen lesznek.

-Mivel tudod gyorsan eldonteni, hogy 3 pont egy egyenesen van (egesz szamok) ?
Kereszt szorzattal.

-Hogyan tudod gyorsan kiszamolni, hogy egy pont melyik osztalyba kerul ?
Kiveszel ket tetszoleges elemet, aztan megnezed, hogy illeszkedik-e a 3
pont egy egyenesre. Ez azt jelenti, hogy egy halmazt 2 ponttal meghatarozhatsz
es nem kell letarolnod az osszes elemet.

Alg:
Beolvasolol n elemet amibol meghatarozod a 3 halmazt valami brute-force algoritmussal.
Persze nem biztos, hogy rogton meg lesz a 3 halmaz.
Aztan meg elkezded venni sorban az elemeket es megnezed, hogy belepasszol-e valamelyik
halmazba. Ha nem akkor vege, egyebbkent meg vegig csinalod minden elemre. O(n) igy.

Azt, hogy hany elem kell egy halmaz letrehozasahoz, most mar pontosan nem emlekszem,
es az elmem nem vag nagyon. Azt hiszem 4. A 3 az meg keves, mert akkor lehetnek
atfedesek az egyenesek kozott.

Sikert !

g

"Alg:
Beolvasolol n elemet amibol meghatarozod a 3 halmazt valami brute-force algoritmussal.
Persze nem biztos, hogy rogton meg lesz a 3 halmaz."

Érzésem szerint ez így nem lesz O(n). (Ahol (és a továbbiakban) n az összes pont számossága)
Pl ha az elemek közül n-4 egy halmazba (egyenesre) esik, és 2-2 a másik kettőbe, akkor itt ebben a lépésben legrosszabb esetben n-ig kéne elmenned a brute-force algoritmussal.

Egyébként ennek a 3 halmaznak a meghatározása a kulcs. Ezt próbáltam egyszerűsíteni a 6 pontos felvetésemmel, de én sem látom pontosan, hogy hogyan lehetne O(n) alatt kiválasztani a megfelelő 6 pontot...

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee."
-- Ted Ts'o

Az O(n) az nem azt jelenti, hogy n muvelet igeny, hanem azt, hogy

c1*n+c2, ahol c1,c2 konstansok. Illetve nem is igy van pontosan,
hanem korlattal, de ez most mindegy.

Az, hogy pl:16 elemre brute-force alguritmust alkalmazol, az nem koltseg.
Kb. 50e pont van es ezt kell kb. 0.1 sec alatt elemezni.

Egyebbkent egy halmaz 4 elem pontosan indukal, azaz az elejen 12 elemet
kell beolvasni...

Félreértesz, ezt mind tudom.

"Egyebbkent egy halmaz 4 elem pontosan indukal, azaz az elejen 12 elemet kell beolvasni..."
Csak az a baj, hogy nem tudod garantálni, hogy te pont jó 12 elemet válassz az elején.
Újra az előző példám:
n-4 elem egy egyenesen, és a maradék 4 pont az egyenesen kívül, nem egy egyenesen.
Ebben az esetben nemhogy 12, de még n-4 elemet is tudok neked úgy választani, hogy ne határozza meg a 3 halmazt.
Sőt n-2 elem még mindig csak 2 halmazt határoz meg.
Tehát legroszabb esetet feltételezve mind az n elemre szükséged van azaz a problémát kb visszavezetted saját magára.
Persze véletleníteni lehet akár úgy is, hogy mindig csak 12 pontot választasz véletlenszerűen, és megnézed, hogy meghatároz-e 3 egyenest. De ettől ez még nem lesz O(n), bármennyire is szeretnéd.
Persze átlagos esetben lehet, hogy gyors.

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee."
-- Ted Ts'o

Jogos. A 12 nem hataroz meg egyertelmuen 3 halmazt.
En ezt nem allitottam vagy most nem allitom. :)

Egy picit modositom a dolgot. Legyen inkabb 10 ez a szam.
A kovetkezok miatt:

A fo celunk, hogy elkeruljunk egy szelsoseges kellemetlen esetet.
Ezt (p mint pont):

ppp
ppp
ppp

Tehat, hogy az elso 9 pont igy helyezkedik el. Itt van legalabb
8 egyenes de nekunk csak a fuggoleges a jo mert a kovektkezo elem
pl igy jon.

p
ppp
ppp
ppp

Ez azt jelenti, hogy van biztosan egy halmazod. Tehat az elejen
amikor egy halmazt meghatarozol ezt csak legalabb 4 elemmel teheted.
Utana mar eleg 2 elem a determininalasahoz.
Az utolso ket halmaz meghatarozas mar trivialis es nem feltetlenul
az elejn tortenik. Ez mar az alkotoszabadsag kategoriajaba tartozik
es marginalis problema.

O(n) az ha mondom, hidd el nekem.

Update:

Tehat az utolso ket halmazt akkor tudod meghatarozni, ossze gyult legalabb
5 olyan elem ami nem tartozik az elso halmazhoz a fenti megfontolasok miatt,
picit modositva azt,

Azt hiszem ennel tobb segitseg nem kene a topic inditonak. :)

10 elmben biztos van egy 4 pontot lefedő egyenes. (Ha nincs, akkor nem lefedhető)
7 elsőre (egyenesre) nem illeszkedő pontban biztos van egy 4 pontos egyenes. (Ha nincs, akkor nem lefedhető)
A maradék pontoknak a 3. egyenesre kell ileszkedni vagy, nem lefedhető.

Ha 9..7 pontod maradt és 0 egyenesed van, (az spec eset), ilyenkor 3 pont elég, hogy egyenesnek nevezd.
Ha 6 pontod van 0 egyenesed akkor 3 egyenest rájuk tudsz zuzni, ha kevesebb akkor is lefedhető.
Ha 1 egyenesed van, és 6-5 pontod, akkor 3 pont elég hogy egyenesnek nevezd.
Ha 1 egyenesed van és 4 vagy kevesebb nem használt pötyid tiviális.
Ha 2 egyenesed van, és 3 pötyid akkor azok egy egyenest kell alkotniuk vagy nem lefedhető. Ha 1 vagy 2 pötyid trivi.

szerk:
Mint ahogy mások észrevették, nem kell 4 pöttyi, elég még keresendő egyenesszám +1 pötyi, és talán szebb is :)

"Beolvasolol n elemet amibol meghatarozod a 3 halmazt valami brute-force algoritmussal.
Persze nem biztos, hogy rogton meg lesz a 3 halmaz."
"Egyebbkent egy halmaz 4 elem pontosan indukal, azaz az elejen 12 elemet
kell beolvasni..."
"A 12 nem hataroz meg egyertelmuen 3 halmazt.
En ezt nem allitottam vagy most nem allitom. :)"

De, állítottad, maximum nem erre gondoltál. :)

Ha jól értem az algoritmusod, akkor tetszik:
Tehát veszel 10 tetszőleges pontot, majd megkeresed azt az egyenest (a 3 közül), ami legalább 4 ponton áthalad. (Ha ilyen nincs, a feladat nem megoldható)
Ez lesz az egyik keresett egyenes.

Veszel 5 olyan pontot ami nem esik erre az egyenesre.(Ha ilyen nincs, azaz max 4 ilyen pont van, akkor trivi.)
Keresel egy másik egyenest (a kettő közül), ami legalább 3 ponton átmegy. (Ha ilyen megint nincs, akkor megintcsak nem megoldható).
Ez lesz a 2. egyenes.
Ezután veszel 2 pontot, amely nincs egyik egyenesen sem. (Ha ilyen egy sincs, akkor a ponthalmaz lefedhető 2 egyenessel. Ha egy van, akkor választasz egy egyenest ami átmegy rajta.)
Ez a 2 pont meghatározza a 3. egyenest.

Majd megnézed, hogy van-e olyan pont, ami nem tartozik egyik egyeneshez sem.

Na ez így tényleg O(n).

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee."
-- Ted Ts'o

( tr3w v | 2007. 04. 08., v – 15:31 )

Hangosan gondolkodom:

Ha a 3 egyenes minden pontot lefed, akkor bármelyik 6-ot is.
Pillanatra tegyük fel, hogy kiválasztottunk 6 pontot úgy, hogy csak 2-2 van egy egyenesen.
Ekkor van konstans számú variációnk egyenesekre (a 6 pontot hányféleképpen lehet összekötni), és csak azt kell kipróbálni, hogy ezek közül melyik fedi le az n pontot.
Ez nyilván O(n).

Már csak ki kell választanunk a 6 pontot úgy, hogy csak 3 egyenessel lehessen lefedni. (Ha ilyen nincs, akkor a teljes ponthalmaz lefedhető 3-nál kevesebb egyenessel.)
Na most érzésem szerint ez is O(n)-ben megoldható. Max tévedek. :)

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee."
-- Ted Ts'o

A 6 pont kiválasztására:

Vegyük az első 6 pontot. Nézzük az összes lehetséges fedő egyenest. Ha mind olyan, hogy egy egyenesen 2 pont van, akkor örülünk.
Ha van olyan variáció, hogy egy egyenesen 2-nél több pont van, akkor a "fölös" pontokat kidobjuk és veszünk helyettük másokat. Ezt ismételjük a megfelelő 6 pont eléréséig. Ha nincs ilyen 6 pont, akkor 3-nál kevesebb egyenessel is lefedhető a halmaz. (Ekkor az utolsó 6-osból kihozható a 2 (vagy 1) egyenes egyenlete.)
Mivel minden pontot maximum egyszer veszünk be, és dobunk ki, ezért ez O(n) vizsgálat, és a 6 pont vizsgálata továbbra is O(1).

Érzésem szerint ez így működik, de át kéne még gondolni...

(Ha összesen nincs 6 pont, azt külön kell kezelni, de nem túl nehéz. :) )

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee."
-- Ted Ts'o

( turul16 v | 2007. 04. 08., v – 17:12 )

Gondoltam agyalok egy kicsit, ha haza jöttem, de látom már megoldottátok :)

( imp | 2007. 04. 09., h – 21:24 )

bár már biztos megoldottátok 3-ra, most legyen k egyenesünk. tudtok-e O(k*n)-nál jobb algoritmust?

( pts | 2007. 04. 18., sze – 19:04 )

Nekem is van egy O(n)-es megoldásom, ha n pont van, melyek elemei k db egyenes uniójának. Az O() becslésben k-t konstansnak veszem, ami kicsit fényezi a helyzetet, mert a megoldásom k-ban exponenciális. Feltételezzem, hogy nincs két pont, amely egybeesne.

Ha n <= k, akkor minden ponthoz adjunk vissza egy egyenest, amin az adott pont rajta van, és készen vagyunk. Ellenkező esetben n >= k+1. Vegyünk k+1 db pontot. A skatulyelv alapján a k+1 db pontot (mint elemet) és a k db keresett egyenest (mint skatulyát) tekintve van közöttük két olyan pont, és egy keresett egyenes, hogy mindkét pont rajta van a keresett egyenesen. Ha tehát van k+1 db pont, akkor az általuk meghatározott (k+1)*k/2 db egyenes között van olyan, amely a keresett egyenesek egyike. Hogy melyik ez az egyenes, nem tudjuk, de nem is kell: visszalépéssel végigpróbáljuk mindet. (A buta végigpróbálások miatt olyan lassú az algoritmus.)

Tehát az (n,k) méretű problémát O(n) lépésben visszavezettük (k+1)*k/2 db (nn,k-1) méretű problémára. Itt az nn kicsit kevesebb, mint n, mert az épp megtalált egyenesen levő pontokat a további vizsgálatból kizárjuk.

A továbbiakban nem mondok újat, csak szemléltetem a k=1, k=2 és k=3 eseteket.

Nézzük, hogy k=1 esetén mit kell csinálni: veszünk 2 pontot, és az általuk meghatározott egyenesre rápakoljuk az összes többi pontot. Ha nem sikerül, meghiúsulást adunk vissza, ha sikerül, akkor a megtalált egyenest. Ha nincs 2 pont, akkor egy tetszőleges egyenest adunk vissza, amin az összes (0 vagy 1 db) pont rajta van.
Mindez O(n) lépésben megoldható.

k=2 esetén veszünk 3 pontot és az általuk meghatározott egyeneseket (legfeljebb 3 különböző egyenes). (Ha nincs 3 db pont, akkor minden ponthoz visszaadunk egy olyan egyenest, amin az adott pont rajta van.) Az összes egyenest végigpróbáljuk: egy adott egyenesre O(n) lépésben elfelejtjük azokat a pontokat, melyek rajta vannak, és a maradék pontokra, k=1 paraméterrel meghívjuk önmagunkat (további O(n) lépés). Összesen tehát O(1)+3*(O(n)+O(n))=O(n) lépés.

k=3 esetén veszünk négy pontot és az általuk meghatározott egyeneseket (legfeljebb 6 különböző egyenes). (Ha nincs 4 db pont, akkor minden ponthoz visszaadunk egy olyan egyenest, amin az adott pont rajta van.) Az összes egyenest végigpróbáljuk: egy adott egyenesre O(n) lépésben elfelejtjük azokat a pontokat, melyek rajta vannak, és a maradék pontokra k=2 paraméterrel meghívjuk önmagjunkat (további O(n) lépés). Összesen tehát O(1)+6*(O(n)+O(n))=O(n) lépés.

Nézzük kicsit pontosabban a becslést: hányszor kell végigolvasni a pontok listáját.

k=1 esetén egyszer elég végigolvasni (egy egyenesre rakjuk fel a rajta levő pontokat).

k=2 esetén legfeljebb három egyenesünk van, a listát minden egyenesre végigolvassuk egyszer (az egyenesre illeszkedő pontok törléséhez), és a maradék listára meghívjuk magunkat k=1-gyel (további 1 végigolvasás). Összesen tehát 3*(1+1)=6 végigolvasás.

k=3 esetén legfeljebb hat egyenesünk van, a listát minden egyenesre végigolvassuk egyszer (az egyenesre illeszkedő pontok törléséhez), és a maradék listára meghívjuk magunkat k=2-vel (további 6 végigolvasás).
Összesen tehát 6*(1+6)=42 végigolvasás. Az élet, a világmindenség meg minden.