Условие
Треугольник
На плоскости даны 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
Подсказка
Эта задача к графам никакого отношения не имеет. Но
с другой стороны, это ничто иное, как предыдущая задача, в которой граф
явно не задан. Впринципе, можно построить полный граф (вес ребра - длина
отрезка между точками) и дальше использовать предыдущую задачу. Хотя можно
(и, наверно, более правильно) вообще никакого графа не строить, что
большинство и делает.
Решение
Скачать архив тестов
Источники и прецеденты использования
|
|
|
Курс |
|
предмет |
информатика |
|
Название |
Основы программирования на языке Паскаль |
|
Класс |
8 |
|
Автор |
Матюхин Виктор Александрович |
|
Место проведения |
Московская гимназия на Юго-Западе N1543 |
|
задача |
|
Номер |
159 |
