Одна из задач на геометрию с регионального этапа Всероссийской олимпиады школьников 2009 года, в которой используется интересная идея и совсем немного комбинаторики.
Точек довольно много, чтобы перебрать все тройки и проверить, составляют ли они равнобедренный треугольник. Такое решение на олимпиаде набирало 40 баллов из 100.
Давайте для начала будем перебирать лишь одну вершину - противоположную основанию. Если теперь выделить множество вершин, равноудалённых от выбранной, то все их попарные комбинации будут образовывать основание равнобедренного треугольника. С одним лишь исключением, что этот треугольник может быть вырожденным, если все три точки окажутся на одной прямой.
В решении будем использовать всю мощь стандартной библиотеки, к тому же удобно сделать подстановку x и y вместо first и second (как мы уже делали в задаче 628):
Считывание данных благодаря подстановкам очень читаемо:
Основное решение тоже довольно короткое. Стоит обратить внимание на используемый тип long long для результата и для вычисления расстояния между точками (кстати, в очередной раз мы не берём корень, чтобы не возиться с точностью вещественных чисел).
В map для каждой возможной длины бокового ребра (точнее, квадрата его длины) подсчитывается количество точек. А второй вложенный цикл проходит по всем длинам и вычисляет количество пар, которые можно получить, по формуле количества сочетаний из n по 2.
Чтобы посчитать количество вырожденных равнобедренных треугольников переберём все пары точек, тогда координаты третьей вершины однозначно определяются. Проверим, есть ли эта вершина во входных данных, для этого сложим все точки в set:
При выводе количество вырожденных треугольников делим пополам, потому что каждый из них посчитался дважды (для каждой вершины основания):
Важным замечанием в этом решении является то, что не существует равносторонних треугольников с целочисленными координатами, потому что в таком случае мы бы посчитали их три раза. Тогда, аналогично подсчёту вырожденных треугольников, пришлось вычесть и их.
Предыдущий выпуск: Задача 26. Две окружности
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.
