KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

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.

Our web pages are supported by:   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