ЗАДАЧИ
problems.ru |
О проекте
|
Об авторах
|
Справочник
Каталог по темам | по источникам | |
|
Задача 64181
УсловиеТреугольник На плоскости даны N точек. Никакие две точки не совпадают, никакие три не лежат на одной прямой. Найдите треугольник с вершинами в этих точках, имеющий наименьший возможный периметр. Входные данные Во входном файле INPUT.TXT записано сначала число N - количество точек (3<=N<=50), а затем N пар вещественных чисел, задающих координаты точек. Выходные данные В выходной файл выведите три числа - номера точек, которые должны быть вершинами треугольника, чтобы его периметр был минимален. Если решений несколько выведите любое из них. Примечание Если у вас есть две точки, и координаты одной из них X1,Y1, а другой X2,Y2, то расстояние R между ними можно вычислить по формуле: R:=sqrt((X1-X2)*(X1-X2)+(Y1-Y2)*(Y1-Y2)); Здесь R должна быть переменной вещественного типа (например, real), а sqrt - стандартная функция, вычисляющая квадратный корень. Пример файла INPUT.TXT 5 0 0 1.3 0 -2 0.1 1 0 10 10 Пример файла OUTPUT.TXT 1 2 4 ПодсказкаЭта задача к графам никакого отношения не имеет. Но с другой стороны, это ничто иное, как предыдущая задача, в которой граф явно не задан. Впринципе, можно построить полный граф (вес ребра - длина отрезка между точками) и дальше использовать предыдущую задачу. Хотя можно (и, наверно, более правильно) вообще никакого графа не строить, что большинство и делает. РешениеИсточники и прецеденты использования
|
© 2004-...
МЦНМО
(о копирайте)
|
Пишите нам
|
![]() |
Проект осуществляется при поддержке