Задача №1208. Треугольники
Разбор добавил Александр Чистяков
Сразу отметим, что в целочисленных координатах невозможно разместить вершины равностороннего треугольника. Поэтому, если треугольник равнобедренный, то у него равны только две стороны. Для каждой из вершин создадим массив свободных векторов, соединяющих текущую вершину с остальными (Для опорной вершины 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) составление списков свободных векторов + сортировки списков + анализ результата для каждой вершины.
Сдать: для сдачи задач необходимо войти в систему
46
statement