ВУЗ:
Составители:
Рубрика:
Пусть имеется трубопровод , заданный прямой линией на
плоскости Ax+By+C=0 и два города с координатами (x1,y1),
(x2,y2). Необходимо соединить эти два города с трубопроводом ,
истратив при этом наименьшее число труб; указать суммарную
длину использованных труб и две точки где происходит
соединение трубопроводов.
Входные данные
Целые числа -100000<=A,B,C<=100000 - параметры трубопровода
-100000<=X1,Y1<=100000 - координаты первого города
-100000<=X2,Y2<=100000 - координаты второго города
Выходные данные
В первой строке суммарная длина использованных труб
Во второй и третьей соответственно координаты точек соединения
трубопроводов
2. Алгоритм решения
Рассмотрим две возможности
1). Точки лежат с разных сторон от прямой. Тогда для их
соединения достаточно опустить на прямую перпендикуляры из
этих точек. На выходе получим сумму длин этих перпендикуляров
и их точки пересечения с прямой.
2). Точки лежат по одну сторону от прямой. Здесь возможны 3
случая
а) Одна точка соединяется с другой, из которой затем опускается
перпендикуляр на прямую. На выходе: длина перпендикуляра плюс
расстояние между точками, координаты точки пересечения
Страницы
- « первая
- ‹ предыдущая
- …
- 58
- 59
- 60
- 61
- 62
- …
- следующая ›
- последняя »
