Сразу отметим, что в целочисленных координатах невозможно разместить вершины равностороннего
треугольника. Поэтому, если треугольник равнобедренный, то у него равны только две стороны.
Для каждой из вершин создадим массив свободных векторов, соединяющих текущую вершину с остальными
(Для опорной вершины V1(x1,y1) и соединяемой V2(x2,y2) таким вектором будет вектор (x2-x1, y2-y1)).
Обратим внимание на то, что равнобедренный треугольник может образовывать только такая тройка вершин
(Vi;Vj;Vk), для которой длины векторов ViVj и ViVk равны. При этом, нулевую площадь этот треугольник
будет иметь только в случае, если вектор ViVj = -ViVk (по условию точки не совпадают).
Для каждой вершины отсортируем массив свободных векторов, определив оператор < следующим образом:
1)Из двух векторов различной длины меньше тот, длина которого меньше;
2)При равенстве длин, меньше тот, у которого косинус угла между сравниваемым вектором и вектором (1;0)
меньше (это нужно для того, чтобы вектора образующие треугольник нулевой площади оказались рядом после
сортировки).
Покажем теперь, как используя результат сортировки, найти количество равнобедренных треугольников,
имеющих общую вершину V1. За один проход по полученному массиву можно выделить непрерывные участки
свободных векторов, имеющих одинаковую длину. Каждая пара таких векторов, не лежащих на одной прямой,
будет образовывать равнобедренный треугольник. Предположим, что ни какие два вектора не лежат на
одной прямой, тогда, если у нас выделились отрезки длинами X1, X2, ... , Xp, то всего из точки V1
выходит X1*(X1-1)/2 + X2*(X2-1)/2 + ... + Xp*(Xp-1)/2. Чтобы найти количество треугольников нулевой
площади, достаточно ещё раз пройтись по массиву векторов и посчитать количество соседних пар
векторов одинаковой длины и с одинаковым косинусом угла с осью Ox (рядом такие пары окажутся
благодаря второму условию в операторе сравнения).
Проделав данную процедуру для каждой вершины и просуммировав значения мы получим ответ на вопрос.
Общая сложность алгоритма: O(N^2 + N^2*logN + N^2) составление списков свободных векторов +
сортировки списков + анализ результата для каждой вершины.
Петя достаточно давно занимается в математическом кружке, поэтому он уже успел не только правила выполнения простейших операций, но и такое достаточно сложное понятие как симметрия. Для того, чтобы получше изучить симметрию Петя решил начать с наиболее простых геометрических фигур – треугольников. Он скоро понял, что осевой симметрией обладают так называемые равнобедренные треугольники. Поэтому теперь Петя ищет везде такие треугольники.
Напомним, что треугольник называется равнобедренным, если его площадь положительна, и у него есть хотя бы две равные стороны.
Недавно Петя, зайдя в класс, увидел, что на доске нарисовано nточек. Разумеется, он сразу задумался, сколько существует троек из этих точек, которые являются вершинами равнобедренных треугольников.
Требуется написать программу, решающую указанную задачу.
Входные данные
Входной файл содержит целое число n (3 ≤ n ≤ 1500). Каждая из последующих строк содержит по два целых числа – xiи yi– координаты i-ой точки. Координаты точек не превосходят 109 по абсолютной величине. Среди заданных точек нет совпадающих.
Выходные данные
В выходной файл выведите ответ на задачу.
Разбалловка для личной олимпиады
Тесты 1-2 — из условия. Оцениваются в 0 баллов.
Тесты 3-13 — n не превосходит 500. Группа тестов оценивается в 40 баллов.
Тесты 14-28 — дополнительных ограничений нет. Группа тестов оценивается в 60 балла (вместе с предыдущими группами — 100 баллов).
Баллы начисляются за прохождение всех тестов группы и всех тестов предыдущих групп. При выставлении баллов за отдельные тесты каждый тест (кроме тестов из условия) оценивается в 4 балла.