Самое большое пастбище Фермера Джона может быть представлено как 2D-решётка
квадратных ячеек (как большая шахматная доска). В настоящий момент \(N\) коров
занимают некоторые из этих ячеек (\(1 \leq N \leq 200\)).
ФД хочет построить забор, который огородит квадратный регион ячеек. Стороны
этого квадрата должны быть параллельны осям координат. И он может быть маленьким,
вплоть до одной ячейки. Помогите ФД посчитать количество различных подмножеств коров,
которые он может огородить таким регионом. Заметим, что пустое подмножество
также нужно считать.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит одно целое число \(N\). Каждая из последующих \(N\)
строк содержит два разделённых пробелом целых числа, указывающих \((x,y)\) координаты
ячейки соответствующей коровы. Все \(x\) координаты различны. Все \(y\) координаты различны.
Все \(x\) и \(y\) координаты в интервале \(0 \ldots 10^9\).
Заметим, что хотя координаты ячеек неотрицательны, квадратная огороженная
область может быть распространена на ячейки с отрицательными координатами.
ФОРМАТ ВЫВОДА (на экран / stdout):
Количество подмножеств коров, которые ФД сможет огородить. Можно доказать,
что это количество поместится в 32-битное целое.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
0 2
2 3
3 1
1 0
|
14
|