Az S. 100. feladat (2015. szeptember)

S. 100. Adott \(\displaystyle N\) (\(\displaystyle 1\le N\le 300\;000\)) db négyzet, melyek oldalai párhuzamosak a koordináta-rendszer tengelyeivel. Minden négyzet pontosan \(\displaystyle K\times K\)-as méretű, ahol (\(\displaystyle 1\le K\le 1\;000\;000\)). Adottak a négyzetek középpontjai az \(\displaystyle (x; y)\) koordinátákkal (\(\displaystyle -1\;000\;000\le x, y\le 1\;000\;000\)). Optimális esetben a négyzetek nem lógnak egymásba, viszont előfordulhat, hogy egy vagy több négyzetpárnak mégis van közös területe.

A program olvassa be a standard input első sorából \(\displaystyle N\)-et, \(\displaystyle K\)-t, majd a következő \(\displaystyle N\) sorból a középpontokat: \(\displaystyle x_i\), \(\displaystyle y_i\), majd írjon a standard output első és egyetlen sorába: 0, t, ha nincs egymásba lógó négyzetpár, -1-et, ha több négyzetpár is egymásba lóg és a közös terület nagyságát, ha pontosan egy négyzetpár lóg egymásba.

Magyarázat: az 1-es és a 3-as négyzetek lógnak egymásba.

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 s100.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ő 2015. október 12-én LEJÁRT.

Statisztika:

25 dolgozat érkezett.
10 pontot kapott:	Alexy Marcell, Dóczi András, Erdős Márton, Gáspár Attila, Mernyei Péter, Nagy Nándor, Noszály Áron, Zalavári Márton, Zarándy Álmos.
8 pontot kapott:	3 versenyző.
7 pontot kapott:	2 versenyző.
5 pontot kapott:	2 versenyző.
4 pontot kapott:	1 versenyző.
3 pontot kapott:	3 versenyző.
1 pontot kapott:	1 versenyző.
0 pontot kapott:	4 versenyző.

A KöMaL 2015. szeptemberi informatika feladatai