 |
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:
| Bemenet (a / jel sortörést helyettesít) | Kimenet (a / jel sortörést helyettesít) |
| -1 -1 / 1 -1 / 1 1 / 2 / -1 1 / 2 2 | 8 / 12 |
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:
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