Даны координаты четырех деревень на плоскости(х1,у1,х2,у2,х3,у3,х4,у4). турист может начинать поход с любой деревни, но он должен посетить все деревни и вернуться в исходную деревню. определите длину самого оптимального маршрута движения туриста. координаты (-40.5,20.8,20.23,60.7,80.32,-2.37,-5.8,-300.5).

169

382

Посмотреть ответы 2

Ответы на вопрос:

ivanchistyakov

Информатика

4,6(16 оценок)

Для начала вычислим расстояния между точками, это сделать легко через вычисление длян векторов обозвав точки в порядке следования a b c d получим ab = 72,6645917899 ac = 123,0197463824 ad = 323,1683462222 bc = 87,105520491 bd = 362,136715758 cd = 310,3290415027 т.к. маршрут кольцевой, то из какой деревни начинать не существенно, будем считать, что всегда выходим из а, тогда существует всего 6 маршрутов a-b-d-c-a 868,1500954331 a-b-c-d-a 793,2675000058 a-c-d-b-a 868,1500954331 a-c-b-d-a 895,4303288536 a-d-b-c-a 895,4303288536 a-d-c-b-a 793,2675000058 наиболее оптимальных 2 a-b-c-d-a и a-d-c-b-a, что логично т.к. это мы ходим в разные стороны, да и собственно маршрутов-то оказывается разных всего 3 : ) ответ 793,2675000058