Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
 Already signed up? New to KöMaL?

# Problem S. 100. (September 2015)

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 pont)

Deadline expired on October 12, 2015.

### Statistics:

 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