Matematika feladatok
-
#1901
na ez má csak jó....
A megoldás Kezes Balázs érsekújvári diák munkája.
1. Rajzoljunk meg egy kört az összes pont körül. Nyilvánvaló, hogy ezt lehet kisebbíteni.
2. Kisebbítsük a kört az olyan A pont megkeresésével, amely a legtávolabb van a középponttól, és rajzoljuk egy új kört ugyanazzal a középponttal és a körvonala haladjon át az A ponton. Ezzel létrehoztunk egy kisebb kört, amelyben szintén benne van az összes pont, de most áthalad az A ponton ahelyett, hogy körülötte lenne.
3. Ha a kör áthalad 2 vagy több ponton, akkor ugorjunk a 4. lépéshez. Ellenkező esetben kisebbítsük a kört a kör közepének az A pont felé valő tolásával, amíg nem érint egy másik B pontot a többi pontból.
4. Ennél a pontnál már van egy körünk, ami kettő vagy több ponton már áthalad. Ha a kör körvonala tartalmaz, egy olyan körív intervallumot, amely nagyobb mint a kör kerületének a fele, és semmilyen pont nem tartózkodik rajta, akkor a kört lehet kisebbíteni. Az ilyen intervallumot pont-mentes intervallumnak fogjuk nevezni. Legyenek a D és E pontok ezen a pont-mentes intervallum végein. Miközben a D és E pontokat a körvonalon tartjuk, kisebbítsük a kör átmérőjét amíg a. az átmérő távolsága nem |DE|, vagy b. a kör körvonala nem érint egy harmadik F pontot.
Az a. esetben végeztünk. A b. esetben meg kell vizsgálnunk, hogy van-e a kerület felénél nagyobb pont-mentes intervallum. Ha nincs, akkor végeztünk. Ellenkező esetben meg a három pontnak egy olyan köríven kell feküdnie, amely rövidebb mint a kerület fele. Meg kell ismételnünk a 4. lépést a két külső ponttal.
Az első három lépés lineárisan függ a pontok mennyisségétől. A 4. lépésben minden új F pont megtalálása is lineárisan függ a pontok mennyisségétől. De az F pont megtalálása nem garantálja az algoritmus végét, és az addig ismétlődik, amíg van pont-mentes intervallum, melynek nagysága nagyobb mint a kerületnek a fele. Legfeljebb (n-2)-ször kell ismételni a 4. lépést, ami O(n2) időbonyolultságot eredményez.