페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#3812

Square Overlap 1초 128MB

문제

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


입력

* 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.


출력

* 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.


예제1

입력
4 6
0 0
8 4
-2 1
0 7
출력
20

INPUT DETAILS:

There are 4 squares, each of size 6 x 6. The first square is centered at (0,0), and so on.

OUTPUT DETAILS:

Pastures #1 and #3 overlap in 20 units of area.


출처

USACO 2013 January Silver

역링크 공식 문제집만