D. Гейзеры
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Долина, в которой живут Мэнни, Сид и Диего, может быть представлена как двумерная плоскость. Введем на этой плоскости координатные оси. Ось OX горизонтальная и направлена с запада на восток, ось OY вертикальная и направлена с юга на север. На этой плоскости расположены $$$n$$$ гейзеров, каждый гейзер представляет из себя точку. Используя данные о расположении гейзеров, друзья хотят оценить, насколько нестабильна сейсмическая обстановка в их долине.

Назовем тройку гейзеров плохой, если треугольник, вершинами которого являются гейзеры, удовлетворяет всем следующим свойствам:

  • он невырожденный,
  • прямоугольный,
  • равнобедренный,
  • как минимум одна из его сторон параллельна OX или OY,
  • на сторонах треугольника не лежат другие гейзеры, кроме трех, которые лежат в вершинах.

Друзья считают, что чем больше плохих троек гейзеров, тем сейсмическая обстановка нестабильнее. Помогите им посчитать количество плохих троек. Две тройки считаются различными, если есть гейзер, который входит в одну тройку и не входит в другую.

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

В первой строке дано одно целое число $$$n$$$ — количество гейзеров ($$$1 \le n \le 100\,000$$$).

В следующих $$$n$$$ строках дано по два целых числа $$$x_i$$$ и $$$y_i$$$ — координаты точки, в которой находится $$$i$$$-й гейзер ($$$|x_i|, |y_i| \le 10^6$$$). Гарантируется, что никакие два гейзера не располагаются в одной точке.

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

Выведите одно целое число — количество плохих троек гейзеров.

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

ПодзадачаБаллыОграничения Необходимые подзадачи Информация о проверке
112$$$n \le 10$$$первая ошибка
217$$$n \le 50$$$1первая ошибка
319$$$n \le 500$$$1, 2первая ошибка
421$$$n \le 5\,000$$$1–3первая ошибка
531$$$n \le 100\,000$$$1–4первая ошибка
Пример
Входные данные
6
0 0
2 0
2 1
1 1
1 2
0 2
Выходные данные
5