28. óra
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.
Függvény fi(P,Q,R)
cr:=(R.x-Q.x)*(P.y-Q.Y)-(P.x-Q.x)*(R.y-Q.y)
Ha cr < 0
akkor fi := -1
különben Ha cr>0
akkor fi := 1
különben fi := 0
Elágazás vége
Elágazás vége
Függvény vége
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.
Függvény belső_pont(P,A,B,C)
belső_pont :=
(fi(P,A,B)>=0 és fi(P,B,C) >= 0 és fi(P,C,A) >= 0) vagy
(fi(P,A,B)<=0 és fi(P,B,C) <= 0 és fi(P,C,A) <= 0)
Függvény vége
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)$.
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)|$.
Függvény távolság(P,A,B)
távolság := |P.x*(B.y-A.y)+P.y*(A.x-B.x)+(B.x*A.y-B.y*A.x)|
Függvény vége
