28. óra
Előző óráról maradt: Sokszög háromszögelése
Az algoritmus áttekintése
Az alapötlet a következő: kiválasztunk egy belső átlót, ezzel kettévágjuk a sokszöget, az átlót hozzáadjuk a háromszögeléshez, a két részre pedig rekurzív megoldjuk a problémát.
Ismer tétel, hogy mindig választható belső átló.
Belső átló kiválasztása
- Vesszük a legbaloldalibb legalsó pontot, legyen ez $v$. ($O(n)$ lépés)
- A $v$ szomszédai $u$ és $w$. (Megfelelő adatszerkezettel ez konstans lépés, ügyetlenebb módszerrel $O(n)$.)
- Teszteljük az $uvw$ háromszöget ($O(n)$ lépés): ha nincs benne és határán pont, akkor $uw$ jó átló. Ha van belső pont, akkor a belső pontok közül az $uw$-től legtávolabbival ($v'$) jó átló lesz $vv'$.
Kettévágás
Ha az eredeti csúcsok ciklikus sorrendben $1,2,3,...,n$, a megtalált átló pedig $uw$, ahol $u, akkor a két új rész:
- $u,u+1,u+2,...,w$
- $w,w+1,...,n,1,2,...,u-1$
A csúcsok eredeti sorrendjét megtartva a részek csúcsainak is helyes lesz a ciklikus rendezése.
Geometriai segédeszközök
Forgásirány
Az olimpiai selejtező egyik feladatában írtak alapján:
A forgásirány függvény ($fi(P,Q,R)$) értéke 1, ha a P pont a Q-R szakasztól balra esik; 0, ha vele egy egyenesre esik; illetve -1, ha tőle jobbra esik.
A forgásirány függvény ($fi(P,Q,R)$) értéke 1, ha a P pont a Q-R szakasztól balra esik; 0, ha vele egy egyenesre esik; illetve -1, ha tőle jobbra esik.
A fenti függvény a $\overrightarrow{QR}\,$ és $\overrightarrow{QP}\,$ (XY síkbeli) vektorok vektoriális szorzatának "z" koordinátáját határozza meg, aminek előjele megadja a két vektor egymáshoz viszonyított forgásirányát.
Háromszög belső pontja
Felveszünk egy körüljárást, majd megnézzük, hogy a vizsgált pont mindig ugyanarra az oldalára esik-e. A PAB, PBC, PCA forgásirányokat kell kiszámítani.
Távolság két ponton átmenő egyenestől
Az egyenes egyenletének általános alakja: $e~:~Ax+By+C=0$. A normálegyenlet:
$f(x,y)=\frac{Ax+By+C}{\sqrt{A^2+B^2}}=0$. Pont és egyenes távolsága: $d(P(x_0,y_0),e)=|f(x_0,y_0)|$.
A távolságok rendezéséhez a nevező nem szükséges.
Ha a két pont $(x_1,y_1)$ és $(x_2,y_2)$, akkor a rajtuk átmenő egyenes egyenlete:
$(y-y_1)(x_2-x_1)=(x-x_1)(y_2-y_1)$,
átrendezve:
$0=(x-x_1)(y_2-y_1)-(y-y_1)(x_2-x_1)=x(y_2-y_1)+y(x_1-x_2)+(x_2y_1-y_2x_1)$.
$(y-y_1)(x_2-x_1)=(x-x_1)(y_2-y_1)$,
átrendezve:
$0=(x-x_1)(y_2-y_1)-(y-y_1)(x_2-x_1)=x(y_2-y_1)+y(x_1-x_2)+(x_2y_1-y_2x_1)$.
Tehát a rendezéshez használhatjuk a következő távolságfüggvényt:
$d(x,y)=|x(y_2-y_1)+y(x_1-x_2)+(x_2y_1-y_2x_1)|$.
$d(x,y)=|x(y_2-y_1)+y(x_1-x_2)+(x_2y_1-y_2x_1)|$.