Az S. 161. feladat (2022. április)

S. 161. Egy épület különböző pontjaira vizet kell vezetni. Az épület tervrajzán \(\displaystyle N\) darab pont mutatja ezeket a helyeket. A tervrajzra gondolatban egy koordináta-rendszert illesztünk, amelyen az \(\displaystyle N\) pont mindegyike egész koordinátákra esik. A vezetékeket úgy építik, hogy a pontokat összekötik egyenes csövekkel úgy, hogy bármelyikből bármelyik másikba el lehessen jutni a csöveken haladva. A merev csöveket csak a tervrajzon jelölt pontokban tudjuk elágaztatni és nem is keresztezhetik egymást. Minden cső a koordináta-rendszer egy-egy rácsvonalára kerül és két megadott pontot köt össze. Adjuk meg, hogy legalább milyen hosszú lesz a csővezetékek hossza, ha közvetetten bármely két pontot összekötjük.

Bemenet: az első sor tartalmazza a pontok \(\displaystyle N\) számát. A következő \(\displaystyle N\) sor mindegyike egy-egy pont \(\displaystyle x\) és \(\displaystyle y\) koordinátáját tartalmazza.

Kimenet: a kimenet első és egyetlen sorába a csövek lehető legkisebb összhosszát kell kiírni. Ha nem lehet őket mind összekötni, akkor -1-et kell kiírni.

Minta:

Korlátok: a koordináták abszolút értéke legfeljebb 1000 és \(\displaystyle N \le 30\). Időlimit: 0,5 mp.

Értékelés: a pontok 30%-a kapható, ha az \(\displaystyle x\) koordináta 0 vagy 1 értéke esetén a program helyes kimenetet ad.

Beküldendő egy s161.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ő 2022. május 16-án LEJÁRT.

Statisztika:

4 dolgozat érkezett.
10 pontot kapott:	Sándor Péter.
3 pontot kapott:	2 versenyző.
0 pontot kapott:	1 versenyző.

A KöMaL 2022. áprilisi informatika feladatai