USACO 2013 January Contest, Silver
Problem 2. Square Overlap
Contest has ended.
Log in to allow submissions in analysis mode
Problem 2: Square Overlap [Brian Dean, 2013]
Farmer John is planning to build N (2 <= N <= 50,000) square fenced-in
pastures on his farm, each of size exactly K x K (1 <= K <= 1,000,000).
Pasture i is centered at point (x_i, y_i) with integer coordinates in the
range -1,000,000...1,000,000. However, in his haste to complete his plans,
FJ realizes that he may have accidentally placed two pastures in locations
that overlap (by overlap, this means the two pastures share a positive area
in common). No two pastures share the exact same center point.
Given the locations of each of the planned square pastures, please help FJ
compute the area shared by the two overlapping pastures. Output zero if no
two squares overlap, and -1 if overlap occurs between more than a single
pair of pastures.
PROBLEM NAME: squares
INPUT FORMAT:
* Line 1: Two space-separated integers, N and K. K is guaranteed to
be even.
* Lines 2..1+N: Line i+1 contains the integers x_i and y_i, describing
the center of the ith pasture.
SAMPLE INPUT (file squares.in):
4 6
0 0
8 4
-2 1
0 7
INPUT DETAILS:
There are 4 squares, each of size 6 x 6. The first square is centered at
(0,0), and so on.
OUTPUT FORMAT:
* Line 1: The area shared by the two overlapping squares. Output zero
if no two squares overlap, and -1 if overlap occurs between
more than a single pair of pastures.
SAMPLE OUTPUT (file squares.out):
20
OUTPUT DETAILS:
Pastures #1 and #3 overlap in 20 units of area.
Contest has ended. No further submissions allowed.