Az S. 107. feladat (2016. április)

S. 107. Egy hatalmas négyzethálós terület (\(\displaystyle 10\,000\,000\times 10\,000\,000\)) \(\displaystyle N\) négyzetét (\(\displaystyle 1\le N\le 200\,000\)) egy-egy fa foglalja el. Egy mókus észrevette, hogy bármelyik fáról bármelyikre el tud jutni csak élszomszédos négyzeteken álló fák közötti ugrásokkal. A fákat tartalmazó négyzetek által alkotott összefüggő területben azért lehetnek lyukak, azaz fákat nem tartalmazó négyzetek. Határozzuk meg az erdő külső kerületét, amibe a lyukak nem számítanak bele.

A program olvassa be a standard input első sorából \(\displaystyle N\)-t, majd a következő \(\displaystyle N\) sorból a fák koordinátáit (\(\displaystyle 1\le x, y\le 10\,000\,000\)), és írja a standard output első és egyetlen sorába a kerület nagyságát.

Pontozás és korlátok: A programhoz mellékelt, a helyes megoldás elvét tömören, de érthetően leíró dokumentáció 1 pontot ér. A programra akkor kapható meg a további 9 pont, ha bármilyen hibátlan bemenetet képes megoldani az 1 mp futásidőkorláton belül.

Beküldendő egy tömörített s107.zip állományban a program forráskódja, valamint a program rövid dokumentációja, amely a fentieken túl megadja, hogy a forrás mely fejlesztői környezetben fordítható.

(10 pont)

A beküldési határidő 2016. május 10-én LEJÁRT.

Statisztika:

10 dolgozat érkezett.
10 pontot kapott:	Kiss Gergely, Nagy Ábel, Nagy Nándor, Szakály Marcell.
8 pontot kapott:	1 versenyző.
6 pontot kapott:	1 versenyző.
5 pontot kapott:	2 versenyző.
4 pontot kapott:	1 versenyző.
3 pontot kapott:	1 versenyző.

A KöMaL 2016. áprilisi informatika feladatai