Az S. 20. feladat (2006. október)

S. 20. Adott a síkon n darab pont. Keressük meg azt a legkisebb kört, amely lefedi az összes pontot. A feladatot megoldó program bemenő adatait egy szöveges állományból vegye, amely soronként egy-egy pont X és Y koordinátáját tartalmazza szóközzel elválasztva. A koordináták valós számok, melyek tizedes pontot tartalmazhatnak. A bemenő állományban nincs üres sor, annyi pont koordináta-párját tárolja, ahány sora van.

Az input állomány nevét a parancssorban adjuk meg, például az alábbi módon:

s20.exe adatok.txt.

A program kimenete a standard kimenetre kerül, egy sorban megadja a keresett kör középpontjának X és Y koordinátáját, valamint a kör sugarát. A programokat különböző méretű, legföljebb 10 000 pontot tartalmazó bemeneti állományokkal teszteljük és értékeljük. A pontozásnál az adatok feldolgozásának sebességét is vizsgáljuk, a maximális pontszám eléréséhez a feldolgozásnak néhány perc alatt véget kell érnie. Például az adatok.txt tartalma:

20 10
22.3 8.0
20 2.0

esetén a kimenet:

20.0 6.0 4.0

Beküldendő a program forráskódja (s20.pas, s20.cpp, ...) és rövid dokumentációja (s20.txt, s20.pdf, ...). A dokumentáció nélküli programok legföljebb 7 pontot érnek.

(10 pont)

A beküldési határidő 2006. november 15-én LEJÁRT.

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(n²) időbonyolultságot eredményez.

Forrás.

Implementáció

1.-2.: Beolvasáskor csak megnézzük, hogy melyik pont van a legtávolabb az origótól, ez a távolság lesz a kör sugara, az origó pedig a közepe.

3. Most közelítenünk kell a legtávolabbi ponthoz úgy, hogy a kör középpontja az origó és a legtávolabbi ponton áthaladó egyenes maradjon. Definiáljunk egy függvényt (minKör), ami megmondja egy adott egyenesre és két pontra azt a kört, melynek a körvonala áthalad a körön és a középpontja az egyenesen fekszik.

Az a_a és b_a az A és B pontok távolságai a p egyenestől, ezeket ismerjük. A' és B' pontok legyenek az A és B pontok p-re való levetítései. Ezek egymástól való távolságát is ismerjük (legyen ez a d). A kör sugara érdekel minket és az a_b vagy az b_b, hogy meg tudjuk határozni a kör közepét is. Felírhatunk egy háromismeretlenes egyenletrendszert:

a_b+b_b=d

a_a²+a_b²=r²

b_a²+b_b²=r²

Ezt átalakítjuk:

b_b=d-a_b

a_a²+a_b²=b_a²+b_b²

Behelyettesítünk, és azt kapjuk, hogy

Ebből már kitudjuk számolni a kör sugarát, és a középpontot is. A középpontot pedig úgy, hogy normalizáljuk a p egyenes irányvektorát, beszorozzuk az a_b-vel, és az ebből kapott ponthoz hozzáadjuk az A' koordinátáit.

Visszatérve a 3. lépéshez: Annyit kell tennünk, hogy az összes pontra meghívjuk a függvényünket, ahol a másik pont lesz az origótól legtávolabb levő pont, és az egyenes pedig a legtávolabbi ponton és az origón áthaladó egyenes. Az összes sugár közül mi a legnagyobbat fogjunk venni, hisz ez lesz a legkisebb, aminek a közepe az egyenesen van és körbefedi az összes pontot.

4. Az új egyenesünk, amin fogjuk vizsgálni a pontokat, a körvonal két szélső pontján áthaladó egyenesre merőleges lesz, és áthalad a két szélső pont középértékén. Elvileg a legkisebb körnek, amely áthalad ezen két ponton, e két pont távolsága lenne az átmérője, és a kör középpontja a két pont középértéke lenne. Szóval, ha valamelyik pont távolsága ettől a ponttól kisebb, mint az előbb említett kör sugara, akkor felesleges azt megvizsgálni. A maradék pontokra és meghívjuk a minKör függvényünket, ahol az egyenest a bekezdés elején már meghatároztuk, és a másik pont valamelyik szélső pont (mindegy, hogy melyik pont ez, hisz szimmetrikusak az egyenes alapján). Fontos megjegyezni, hogy minden iterációban kisebbítjük a körünket, és ha ezt nem sikerült megtennünk, akkor az azt jelenti, hogy befejeztük.

Itt már megvan a lehető legkiseb kör, ami még mindig behatárolja az összes pontot, és a közepe az adott egyenesen van. Ha ennek az átmérője pontosan a két pont távolsága, akkor végeztünk. Ellenkező esetben lesz egy harmadik pontunk, ami a körvonalon lesz. Meg kell vizsgálnunk, hogy van-e olyan pont-mentes intervallum, amelynek a hossza nagyobb mint kör sugarának a fele. Ezt pedig úgy határozzuk meg, hogy meghatározzuk mind a három pontra, az adott a pont, a kör középpontja és egy köríven felvett tetszőleges pont által bezárt szöget. Ezeket a szögeket sorbarendezzük. Ezután megvizsgáljuk hogy van-e két egymás után következő pont között nagyobb szög mint 180 fok. Ha igen, akkor ez a két pont lesz az új két szélső pont, és ugrunk a ciklus elejére. Ellenkező esetben végeztünk.

5. Kiírjuk az eredményt.

Statisztika:

13 dolgozat érkezett.
10 pontot kapott:	Csernai Kornél, Kezes Balázs, Szebeni Szilveszter.
7 pontot kapott:	2 versenyző.
4 pontot kapott:	1 versenyző.
3 pontot kapott:	4 versenyző.
2 pontot kapott:	2 versenyző.
1 pontot kapott:	1 versenyző.

A KöMaL 2006. októberi informatika feladatai