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

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

1 секунда

128 мегабайтів

Дуже складна

Найбільше пасовище фермера Джона можна уявити як велику двовимірну сітку квадратних "клітинок" (уявіть величезну шахову дошку). Наразі деякі з цих клітинок займають $n$ корів.

Фермер Джон хоче побудувати паркан, що огороджує квадратну область клітинок. Квадрат має бути орієнтований так, щоб його сторони були паралельні осям $x$ і $y$ , і може бути навіть розміром з одну клітинку. Допоможіть йому підрахувати кількість різних підмножин корів, яких він може огородити в такій області. Зверніть увагу, що порожня підмножина також враховується.

Вхідні дані

Перший рядок містить одне ціле число $n$ ( $1 \leq n \leq 200$ 1 \leq n \leq 200).

Кожен з наступних $n$ рядків містить по два цілих числа — координати $(x, y)$ клітинки з коровою. Усі $x$ координати різні, і всі $y$ координати різні. Усі значення $x$ і $y$ знаходяться у діапазоні $0 \dots 1 0^{9}$ 0 \ldots 10^9.

Зверніть увагу, що хоча координати клітинок з коровами невід'ємні, квадратна огороджена територія може поширюватися на клітинки з від'ємними координатами.

Вихідні дані

Виведіть кількість підмножин корів, яких може відгородити фермер Джон. Можна показати, що це число вміщується у $32$ -бітне знакове ціле число.

Приклади

У прикладі всього $24$ підмножини. Фермер Джон не може створити паркан лише для корів $1$ і $3$ , або лише для корів $2$ і $4$ , тому відповідь дорівнює $24 - 2 = 22$ 24-2=22.

Приклад 1

Приклад 2