Az S. 169. feladat (2023. március)

S. 169. 2 egység magasságú egyenes hasáb alakú tárolóedényt szeretnénk készíteni. Az edény alapjának elkészítéséhez kiindulásként adott egy konvex sokszög, melynek csúcsai a koordináta-rendszer rácspontjaira esnek. Ennek a sokszögnek töröljük egy csúcsát és a csúcshoz kapcsolódó két élét, és összekötjük egy éllel a törölt élek megmaradt csúcspontjait. Az így kialakuló sokszöget tekintjük a tárolóedény alapjának.

Feladatunk, hogy a feltételek szerint adott konvex sokszög esetén határozzuk meg, mekkora a belőle készíthető legnagyobb kapacitású edény kapacitása.

A bemenet első sorában a konvex sokszög csúcsainak \(\displaystyle N\) száma szerepel. A következő \(\displaystyle N\) sorban a csúcsok \(\displaystyle x\) és \(\displaystyle y\) koordinátája pozitív körüljárási irány szerint. A listában a szomszédos pontok a sokszöget alkotó szakaszok végpontjai. Az első és az utolsó csúcs is össze van kötve.

A kimenet első és egyetlen sorába a konvex sokszögből készíthető legnagyobb kapacitású edény kapacitása kerüljön.

Minta:

Magyarázat: az ábrán a \(\displaystyle H\) csúcsot törölve az edény kapacitása 17.

Korlátok: \(\displaystyle 1\le N \le 100\,000\), \(\displaystyle -10^8\le x,y \le 10^8\). Időkorlát: 1 mp.

Értékelés: A pontok 40%-a kapható, ha a program helyes kimenetet ad az \(\displaystyle {N\le 100}\) esetekben.

Beküldendő egy s169.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ó. A dokumentáció tartalmazza a megoldás elméleti hátterét, az esetleg felhasznált forrásokat. Ne tartalmazzon kódrészleteket, azok magyarázata kódkommentek formájában a forrásprogramban szerepeljen.

(10 pont)

A beküldési határidő 2023. április 17-én LEJÁRT.

Statisztika:

3 dolgozat érkezett.
10 pontot kapott:	Horváth Milán, Puppi Barna, Zádor-Nagy Zsombor.

A KöMaL 2023. márciusi informatika feladatai