Квадратное пастбище
Квадратное пастбище
Самое большое пастбище фермера Джона можно рассматривать как большую двумерную сетку квадратных "ячеек" (изобразите огромную шахматную доску). В настоящее время некоторые из этих клеток занимают n коров.
Фермер Джон хочет построить забор, ограждающий квадратную область клеток; квадрат должен быть ориентирован так, чтобы его стороны были параллельны осям x и y. Он даже может быть размером с одну ячейку. Помогите ФД подсчитать количество отдельных групп коров, которых он сможет заключить в такой области. Обратите внимание, что пустое подмножество следует считать одной из облатей.
Входные данные
Первая строка содержит одно целое число n (1 ≤ n ≤ 200). Каждая из следующих n строк содержит два целых числа, обозначающих координаты (x, y) клетки коровы. Все координаты x отличаются друг от друга, все координаты y отличаются друг от друга. Все значения x и y лежат в диапазоне 0 ... 109
.
Обратите внимание, что хотя координаты ячеек с коровами неотрицательны, квадратная огороженная территория может распространяться на ячейки с отрицательными координатами.
Выходные данные
Выведите количество подмножеств коров, которых может отгородить ФД. Можно показать, что это количество укладывается в 32-битное знаковое целое число.
Пример
В примере всего 24 подмножества. ФД не может создать забор, ограждающий только коров 1 и 3 или только коров 2 и 4, поэтому ответ равен 24 − 2 = 16 − 2 = 14.
4 0 2 2 3 3 1 1 0
14
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
420