Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

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.


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