Фермер Джон планирует построить N (2 <= N <= 50,000) квадратных огороженных пастбищ у себя на ферме, каждое размером ровно K x K (1 <= K <= 1,000,000).
Пастбище i имеет центр в точке (xi, yi), с целочисленными координатами в диапазоне -1,000,000...1,000,000. Никакие два пастбища не имеют один и тот же центр.
Вычислите (ненулевую) площадь перекрытия двух квадратных пастбищ. Выведите 0, если никакие два квадрата не перекрываются. Выведите -1 если перекрываются более одной пары квадратов.
PROBLEM NAME: squares
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа, N и K. Гарантируется, что K четное.
* Строки 2..1+N: Строка i+1 содержит целые числа xi и yi, описывающие центр пасбища i.
Формат выходных данных
* Строка 1: Площадь перекрытия двух квадратов. Выведите 0, если никакие два квадрата не перекрываются, выведите -1, если перекрываются более одной пары квадратов.
Примечание
Пастбища #1 и #3 перекрываются на 20 единиц площади.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 6
0 0
8 4
-2 1
0 7
|
20
|