Az S. 153. feladat (2021. május)

S. 153. Van egy derékszögű koordináta-rendszerünk, amelyben kezdetben három pont helyezkedik el. Egymás után újabb pontokat veszünk hozzá a ponthalmazhoz. Minden egyes új pont után szeretnénk tudni, mekkora a legkisebb területű konvex sokszög területe, mely minden eddig felvett pontot tartalmaz – a matematikusok ezt a sokszöget konvex buroknak nevezik. (Egy konvex sokszög tartalmaz egy pontot, ha a pont a sokszög belsejében, élén, vagy csúcsán helyezkedik el.)

Bemenet: Az első három sorban az eredeti három pont $\displaystyle x$ és $\displaystyle y$ koordinátái szerepelnek. A negyedik sorban az ezekhez hozzávett pontok $\displaystyle N$ számát adjuk meg. A következő $\displaystyle N$ sor mindegyike egy újonnan felvett pont $\displaystyle x$ és $\displaystyle y$ koordinátáit tartalmazza.

Kimenet: $\displaystyle N$ sort kell kiírni, melyek mindegyike az $\displaystyle i$-edik pont hozzávétele utáni terület kétszeresét tartalmazza (ez mindig egész szám).

Példa:

Korlátok: $\displaystyle 1\le N\le {10}^{5}$, $\displaystyle -{10}^{8}\le xy\le {10}^{8}$, a koordináták egész számok, a kezdeti három pont nincs egy egyenesen. Időkorlát: 1 mp.

Értékelés: a pontok 30%-a kapható, ha $\displaystyle N\le 100$.

Beküldendő egy s153.zip tömörített állományban a megfelelően dokumentált és kommentezett forrásprogram, amely tartalmazza a megoldás lépéseit, valamint megadja, hogy a program melyik fejlesztői környezetben futtatható.

(10 pont)

A beküldési határidő 2021. június 15-én LEJÁRT.

Az egyetlen 10 pontos megoldáshoz gratulálunk Horcsin Bálintnak:

dok.pdf

A feladat hatékony megoldása implementációtól és egyéb részletektől függetlenül ugyan az volt: Keressük meg azokat a csúcsokat, melyek az új pont felvételével a konvex burkon belülre kerülnek. Ezt meg lehet csinálni Horcsin Bálint megoldása szerint a sokszög eltolásával és egy ügyes rendezési függvénnyel, vagy egyszerű bináris kereséssel is. Ilyenkor két olyan érinitőt keresünk a sokszöghöz, melyek áthaladnak az újonnan felvett ponton.

A komplexitás minden esetben $\displaystyle O(N*log(N))$

Statisztika:

4 dolgozat érkezett.
10 pontot kapott:	Horcsin Bálint.
3 pontot kapott:	2 versenyző.
0 pontot kapott:	1 versenyző.

A KöMaL 2021. májusi informatika feladatai