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 documentationalso describing which developer environment to use for compiling the sourceshould be submitted in a compressed file s100.zip.
(10 pont)
Deadline expired on October 12, 2015.
Statistics:
