eolymp
Соревнования

USACO 2020 December

Квадратное пастбище

Самое большое пастбище фермера Джона можно рассматривать как большую двумерную сетку квадратных "ячеек" (изобразите огромную шахматную доску). В настоящее время некоторые из этих клеток занимают n коров.

Фермер Джон хочет построить забор, ограждающий квадратную область клеток; квадрат должен быть ориентирован так, чтобы его стороны были параллельны осям x и y. Он даже может быть размером с одну ячейку. Помогите ФД подсчитать количество отдельных групп коров, которых он сможет заключить в такой области. Обратите внимание, что пустое подмножество следует считать одной из облатей.

Входные данные

Первая строка содержит одно целое число n (1n200). Каждая из следующих n строк содержит два целых числа, обозначающих координаты (x, y) клетки коровы. Все координаты x отличаются друг от друга, все координаты y отличаются друг от друга. Все значения x и y лежат в диапазоне 0 ... 109.

Обратите внимание, что хотя координаты ячеек с коровами неотрицательны, квадратная огороженная территория может распространяться на ячейки с отрицательными координатами.

Выходные данные

Выведите количество подмножеств коров, которых может отгородить ФД. Можно показать, что это количество укладывается в 32-битное знаковое целое число.

Пример

В примере всего 24 подмножества. ФД не может создать забор, ограждающий только коров 1 и 3 или только коров 2 и 4, поэтому ответ равен 242 = 162 = 14.

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
4
0 2
2 3
3 1
1 0
Выходные данные #1
14
Входные данные #2
16
17 4
16 13
0 15
1 19
7 11
3 17
6 16
18 9
15 6
11 7
10 8
2 1
12 0
5 18
14 5
13 2
Выходные данные #2
420
Источник 2020 USACO Декабрь, Золото