KöMaL - Középiskolai Matematikai és Fizikai Lapok
 English
Információ
A lap
Pontverseny
Cikkek
Hírek
Fórum

Rendelje meg a KöMaL-t!

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

S. 100. We are given \(\displaystyle N\) squares (\(\displaystyle 1\le N\le 300\;000\)) with sides parallel to the coordinate axes. The size of each square is \(\displaystyle K\times K\) (\(\displaystyle 1\le K\le 1\;000\;000\)), and the center of each square is also given by a pair \(\displaystyle (x; y)\) (\(\displaystyle -1\;000\;000\le x, y\le 1\;000\;000\)). Some squares do not overlap, but sometimes one or more pairs of squares overlap with an intersection having positive area.

Your program should read \(\displaystyle N\) and \(\displaystyle K\) from the first line of the standard input, then the \(\displaystyle x_i\), \(\displaystyle y_i\) coordinates from the following \(\displaystyle N\) lines. The first and only line of the standard output should be either 0 if no two squares overlap, or -1 if there are more than one overlapping pairs, or the area of the intersection if there is exactly one pair of overlapping squares.

In the example, ``Példa bemenet'' is a sample input, while ``Példa kimenet'' is the corresponding output. Explanation: squares 1 and 3 overlap.

Scoring and bounds. You can get 1 point for a brief and proper documentation clearly describing your solution. Nine further points can be obtained provided that your program solves any valid input within 1 second of running time.

The source code of your program with a short documentation-also describing which developer environment to use for compiling the source-should be submitted in a compressed file s100.zip.

(10 points)

Deadline expired on 12 October 2015.


Statistics on problem S. 100.
25 students sent a solution.
10 points: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 points:3 students.
7 points:2 students.
5 points:2 students.
4 points:1 student.
3 points:3 students.
1 point:1 student.
0 point:4 students.


  • Problems in Information Technology of KöMaL, September 2015

  • Támogatóink:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
    MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley